chromatic index of $K_6$

hbghlyj

Example 4.4.6. Six friends decide to spend the afternoon playing chess. Everyone will play everyone else once. They have plenty of chess sets but nobody wants to play more than one game at a time. Games will last an hour (thanks to their handy chess clocks). How many hours will the tournament last?

Solution.

Represent each player with a vertex and put an edge between two players if they will play each other. In this case, we get the graph $K_6$:

We must color the edges; each color represents a different hour. Since different edges incident to the same vertex will be colored differently, no player will be playing two different games (edges) at the same time. Thus we need to know the chromatic index of $K_6$.
Notice that for sure $χ'(K_6)≥5$, since there is a vertex of degree 5. It turns out 5 colors is enough (go find such a coloring). Therefore the friends will play for 5 hours.

Interestingly, if one of the friends in the above example left, the remaining 5 chess-letes would still need 5 hours: the chromatic index of $K_5$ is also 5.

Czhang271828

The book Combinatorics with Emphasis on the Theory of Graphs (GTM054) is one of my favourite encyclopaediae on graph theory, from which I adopt the notations $\chi_0(G)$ and $\chi_1(G)$ to distinguish chromatic indices on vertices and edges of $G$ respectively.

One shocking thm from Визинг says that $\max_{v\in V(G)}\deg v -\chi_1(G)\in \{0,1\}$. As a corollary, $\chi_1(K_6)$ is either $5$ or $6$.

Furthermore, those $\cdots =0$ are classified as "graphs in the first category", while the others ($\cdots =1$) are called "graphs in the second category". One conjecture from Визинг says that:

Each planar graph satisfying $\max_{v\in V(G)}\deg v\geq 6$ are in the first category.

• It is proven by Vizing that all graphs with $\max_{v\in V(G)}\deg v\geq 8$ are in the first catogory.
• It is proven by professors in 山东大学 that all graphs with $\max_{v\in V(G)}\deg v= 7$ are in the first catogory.
• $\cdots =6$ is still unknown.
• There exists some planar graphs with $\max_{v\in V(G)}\deg v\in\{2,3,4,5\}$ in the second category (by Визинг).