3-退化图的全染色

作者：杨腾飞; 徐常青^*

来源：山东大学学报(理学版), 2022, 57(06): 61-63.

• 全染色
• 全色数
• 3-退化图

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

• 单位
  河北工业大学