摘要
如果图G的一个正常染色满足任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc(G)表示,是指G的所有线性染色中所用的最少颜色的个数.证明了对于每一个最大度为△围长至少为5的平面图G,lc(G)≤△+2.
A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths.The linear chromatic number lc（G） of the graph G is the smallest number of colors in a linear coloring of G.we prove that plane graphs G with girth g≥5 and maximum degree △ has lc（G）≤△＋5.
出处
《菏泽学院学报》
2010年第2期5-9,共5页
Journal of Heze University
关键词
平面图
线性染色
围长
最大度
Plane graphs
linear coloring
girth
maximum degree
