- Series
- Graph Theory Seminar
- Time
- Tuesday, November 15, 2022 - 3:45pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Yanli Hao – Georgia State University – yhao4@gsu.edu
- Organizer
- Tom Kelly

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.