点击量 ：

第一作者 ： 王维凡

发表时间 ： 2008-01-01

发表刊物 ： 中国科学(A辑:数学)

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

文献类型 ： 期刊

期号 ： 第12期

页面范围 ： 1321-1334

ISSN ： 1674-7216

关键字 ： 线性染色；非负特征图；围长；最大度

摘要 ： 如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc(G)表示,是指G的所有线性染色中所用的最少颜色的个数.证明了:对于每一个最大度为△(G)围长为g(G)的非负特征图G,若存在一个有序对(△,g)∈{(13,7),(9,8),(7,9),(5,10),(3,13)},使得G满足△(G)≥△且g(G)≥g,则lc(G)=「△(G)/2」+1.

是否译文 ： 否