Linear coloring of graphs embeddable in a surface of nonnegative characteristic  

作　　者：WANG WeiFan LI Chao 

机构地区：[1]Department of Mathematics,Zhejiang Normal University,Jinhua 321004,China

出　　处：《Science China Mathematics》2009年第5期991-1003,共13页中国科学：数学（英文版）

基　　金：supported by National Natural Science Foundation of China (Grant No. 10771197);the Natural Science Foundation of Zhejiang Province of China (Grant No. Y607467)

摘　　要：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, we prove that every graph G with girth g(G) and maximum degree Δ(G) that can be embedded in a surface of nonnegative characteristic has $ lc(G) = \left\lceil {\frac{{\Delta (G)}} {2}} \right\rceil + 1 $ if there is a pair (Δ, g) ∈ {(13, 7), (9, 8), (7, 9), (5, 10), (3, 13)} such that G satisfies Δ(G) ? Δ and g(G) ? g.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, we prove that every graph G with girth g(G) and maximum degree Δ(G) that can be embedded in a surface of nonnegative characteristic has lc(G) = Δ(2G )+ 1 if there is a pair (Δ, g) ∈ {(13, 7), (9, 8), (7, 9), (5, 10), (3, 13)} such that G satisfies Δ(G) Δ and g(G) g.

关 键 词：linear coloring graph of nonnegative characteristic GIRTH maximum degree 05C15 

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