Linear coloring of planar graphs with large girth |
| |
Authors: | André Raspaud |
| |
Affiliation: | LaBRI UMR CNRS 5800, Universite Bordeaux I, 33405 Talence Cedex, France |
| |
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 of the graph G is the smallest number of colors in a linear coloring of G. In this paper we prove that every planar graph G with girth g and maximum degree Δ has if G satisfies one of the following four conditions: (1) g≥13 and Δ≥3; (2) g≥11 and Δ≥5; (3) g≥9 and Δ≥7; (4) g≥7 and Δ≥13. Moreover, we give better upper bounds of linear chromatic number for planar graphs with girth 5 or 6. |
| |
Keywords: | Planar graph Linear coloring Girth Maximum degree |
本文献已被 ScienceDirect 等数据库收录! |