Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6423493 | Discrete Mathematics | 2011 | 7 Pages |
Abstract
A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is a 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.Let G be a graph with maximum degree Î(G). In this paper we prove the following results: (1) lc(G)â¤12(Î(G)2+Î(G)); (2) lc(G)â¤8 if Î(G)â¤4; (3) lc(G)â¤14 if Î(G)â¤5; (4) lc(G)â¤â0.9Î(G)â+5 if G is planar and Î(G)â¥52.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Chao Li, Weifan Wang, André Raspaud,