Plane Graphs with Maximum Degree 5 Are 11-Linear-Colorable  

作　　者：Kan WANG Weifan WANG 

机构地区：[1]College of Mathematics,Physics and Information Engineering,Zhejiang Normal University,Zhejiang 321004,P.R.China

出　　处：《Journal of Mathematical Research with Applications》2012年第6期647-653,共7页数学研究及应用（英文版）

基　　金：Supported by the National Natural Science Foundation of China (Grant No. 11071223);the Natural ScienceFoundation of Zhejiang Province (Grant No. Z6090150);Research Project of Zhejiang Educational Committee(Grant No. Y201121311)

摘　　要：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 lc（G） of G is the smallest number of colors in a linear coloring of G. In this paper, we prove that every planar graph G with maximum degree 5 is 11-linear-colorable.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 lc（G） of G is the smallest number of colors in a linear coloring of G. In this paper, we prove that every planar graph G with maximum degree 5 is 11-linear-colorable.

关 键 词：planar graph linear coloring maximum degree. 

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