Linear coloring of graphs embeddable in a surface of nonnegative characteristic |
| |
Authors: | WeiFan Wang Chao Li |
| |
Affiliation: | (1) Department of Mathematics, Zhejiang Normal University, Jinhua, 321004, China |
| |
Abstract: | 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 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. This work was supported by National Natural Science Foundation of China (Grant No. 10771197) and the Natural Science Foundation of Zhejiang Province of China (Grant No. Y607467) |
| |
Keywords: | linear coloring graph of nonnegative characteristic girth maximum degree |
本文献已被 CNKI SpringerLink 等数据库收录! |
|