点击量 ：

第一作者 ： 王侃

发表时间 ： 2011-01-01

发表刊物 ： 数学研究

所属单位 ： 数理与信息工程学院

文献类型 ： 期刊

期号 ： 第1期

页面范围 ： 76-85

ISSN ： 1006-6837

关键字 ： 平面图；线性染色；围长；最大度

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

是否译文 ： 否