Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418324 | Discrete Applied Mathematics | 2014 | 10 Pages |
Abstract
A vertex coloring of a graph GG is linear if the subgraph induced by the vertices of any two color classes is the union of vertex-disjoint paths. In this paper, we study the linear coloring of graphs with small girth and prove that: (1) Every planar graph with maximum degree Δ≥39Δ≥39 and girth g≥6g≥6 is linearly (⌈Δ2⌉+1)-colorable. (2) There exists an integer Δ0Δ0 such that every planar graph with maximum degree Δ≥Δ0Δ≥Δ0 and girth g≥5g≥5 is linearly (⌈Δ2⌉+1)-colorable. The latter result is best possible in some sense.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Wei Dong, Wensong Lin,