Georgia Institute of Technology College of Sciences

The chromatic index $\chi'(G)$ of a graph $G$ is the least number of colors assigned to the edges of $G$ such that no two adjacent edges receive the same color. The total chromatic number $\chi''(G)$ of a graph $G$ is the least number of colors assigned to the edges and vertices of $G$ such that no two adjacent edges receive the same color, no two adjacent vertices receive the same color and no edge has the same color as its two endpoints. The chromatic index and the total chromatic number are two of few fundamental graph parameters, and their correlation has always been a subject of intensive study in graph theory.

By definition, $\chi'(G) \le \chi''(G)$ for every graph $G$. In 1984,  Goldberg conjectured that for any multigraph $G$, if $\chi'(G) \ge \Delta(G) +3$ then $\chi''(G) = \chi'(G)$. We show that Goldberg's conjecture is asymptotically true. More specifically,  we prove that for a multigraph $G$ with maximum degree $\Delta$ sufficiently large, $\chi''(G) = \chi'(G)$ provided $\chi'(G) \ge \Delta + 10\Delta^{35/36}$.  When $\chi'(G) \ge \Delta(G) +2$, the chromatic index $\chi'(G)$ is completely determined by the fractional chromatic index. Consequently,   the total chromatic number $\chi''(G)$ can be computed in polynomial-time in this case.