围长较大的平面图的全染色的一个结果

摘要：

图G的一个k全染色是用k种颜色对图G的顶点集和边集进行染色使得相邻接的或相关联的元素染不同的颜色,图G的全色数χ＂（G）为图G的k-全染色中的最小k值.Behzad和Vizing猜想任意简单图G的全色数都不超过Δ（G）＋2,已经证明了此猜想对最大度不是6的平面图成立,而且最大度不小于9的平面图G的全色数为Δ（G）＋1.本文利用差值转移方法研究了最大度小于9的一些情况,证明了最大度为4,5,6,7,8的平面图G,如果其围长不小于8,则其全色数也为Δ（G）＋1.

关键词：全染色、平面图、全色数

所属期刊栏目：31

分类号：O157.5(代数、数论、组合理论)

资助基金：中央高校基本科研业务费专项基金2010LKSX06;四川文理学院2011年院级科研项目2011Z008y

在线出版日期：2012-06-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：8-10