Document Type
Lecture
Publication Date
12-1-2023
Abstract
The chromatic index χ′(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 χ′′(G) of a graph G is the least number of colors assigned to the edges and vertices 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 coloring number are two of few fundamental graph parameters, and their correlation has always been a subject of intensive study in graph theory. By definition, χ′(G) ≤ χ′′(G) for every graph G. In 1984, Goldberg conjectured that for any multigraph G, if χ′(G) ≥ ∆(G) + 3 then χ′′(G) = χ′(G). The conjecture is shown asymptotically true. More specifically, for a multigraph G with maximum degree ∆ sufficiently large, χ′′(G) = χ′(G) provided χ′(G) ≥ ∆ + 10∆35/36. When χ′(G) ≥ ∆(G)+2,thechromaticindexχ′(G)iscompletelydeterminedbythefractional chromatic index. Consequently, the total chromatic number χ′′(G) can be computed in polynomial-time in this case. In this talk, I will discuss the recent progress and the proof techniques.
Relational Format
presentation
Recommended Citation
Chen, Guantao, "On the coequal values of total chromatic number and chromatic index" (2023). Combinatorics Seminar. 12.
https://egrove.olemiss.edu/math_combinatorics/12
