3-退化图的全染色

Total colorings of 3-degenerate graphs

图G的k-全染色指用k种颜色对图G的顶点和边进行染色,使得相邻或相关联的元素染不同的颜色。图G的全色数是指使得G有一个k-全染色的最小正整数k,记作χ″(G)。Behzad和Vizing独立提出了全染色猜想:对于任意图G,有χ″(G)≤Δ(G)+2。证明了对Δ(G)≥5的3-退化图全染色猜想成立。

A k-total coloring of a graph G is a coloring of the vertices and edges with k colors, such that no two adjacent or incident elements receive the same color. The total chromatic number of a graph G is the smallest integer k such that G has a k-total coloring, denoted by χ″(G). Behzad and Vizing independently proposed the Total Coloring Conjecture that χ″(G)≤Δ(G)+2 for any graph G. In this paper, it is proved that the 3-degenerate graph with Δ(G)≥5 satisfies the total coloring Conjecture.