3-退化图的全染色

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