最大度为6图是19-线性可染的  

19-linear-colorable Graphs with Maximum Degree 6

作　　者：王侃[1] 

机构地区：[1]浙江师范大学数理与信息工程学院,浙江金华321004

出　　处：《绍兴文理学院学报》2011年第9期5-6,10,共3页Journal of Shaoxing University

基　　金：国家自然科学基金资助项目(11071223);浙江省自然科学基金重点项目(Z6090150);浙江省教育厅科研项目(Y201121311)

摘　　要：图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.

关 键 词：线性染色 线性色数 最大度 

分 类 号：O157.5[理学—数学]