围长至少为6的平面图的线性染色

摘要：

如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc(G)表示,是指G的所有线性染色中所用的最少颜色的个数.论文证明了对于每一个最大度为△(G)围长至少为6的平面图G有lc(G)≤[△(G)/2]+3,并且当△(G)(∈/){4,5,…,12)时,lc(G)≤[△(G)/2]+2.

关键词：平面图、线性染色、围长、最大度

所属期刊栏目：25

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

资助基金：国家自然科学基金10771197;浙江省自然科学基金重点项目Z6090150

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

页数：共9页

页码：487-495