摘要
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.
基金
supported by National Natural Science Foundation of China (Grant No. 10771197)
the Natural Science Foundation of Zhejiang Province of China (Grant No. Y607467)
