| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427581 | Information Processing Letters | 2012 | 5 Pages |
Abstract
A proper vertex coloring of a graph is called linear if the subgraph induced by the vertices colored by any two colors is a set of vertex-disjoint paths. The linear chromatic number of a graph G, denoted by lc(G), is the minimum number of colors in a linear coloring of G. In this paper, we show lc(G)⩽Δ(G)+7 for a planar graph G with maximum degree Δ(G).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
