摘要
图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图G是一些点不交的路的并,则称这个正常染色为图的线性染色.图G的线性色数是指G的所有线性染色中所用的最少颜色的个数.证明了:最大度为6的图是19-线性可染的.
A linear coloring of a graph G is a proper vertex coloring such that the graph induced by the vertices of any two color classes is the union of vertex - disjoint paths. The linear chromatic number of the graph G is the smallest number of colors in a linear coloring of G. This paper proves that every graph G with maximum degree 6 is 19 - linear - colorable.
出处
《绍兴文理学院学报》
2011年第9期5-6,10,共3页
Journal of Shaoxing University
基金
国家自然科学基金资助项目(11071223)
浙江省自然科学基金重点项目(Z6090150)
浙江省教育厅科研项目(Y201121311)
关键词
线性染色
线性色数
最大度
linear coloring
linear chromatic number
maximum degree
