New Upper Bounds on Linear Coloring of Planar Graphs  

作　　者：Bin LIU Gui Zhen LIU 

机构地区：[1]Department of Mathematics,Ocean University of China [2]School of Mathematics,Shandong University

出　　处：《Acta Mathematica Sinica,English Series》2012年第6期1187-1196,共10页数学学报（英文版）

基　　金：Supported by National Natural Science Foundation of China (Grant Nos. 61070230, 10971121 and 61103199);NSFSP of China (Grant No. ZR2009AM009)

摘　　要：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. In this paper, it is proved that every planar graph G with girth g and maximum degree A has （1） lc（G） ≤ △ ＋ 21 if △ ≥ 9; （2） lc（G） ≤[△/2]＋ 7 if g≥5; （3） lc（G） ≤ [△/2]＋2ifg≥7and△ ≥7.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. In this paper, it is proved that every planar graph G with girth g and maximum degree A has （1） lc（G） ≤ △ ＋ 21 if △ ≥ 9; （2） lc（G） ≤[△/2]＋ 7 if g≥5; （3） lc（G） ≤ [△/2]＋2ifg≥7and△ ≥7.

关 键 词：Linear coloring planar graph GIRTH 

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