| Plane Graphs with Maximum Degree 5 Are 11-Linear-Colorable |
| Received:June 21, 2011 Revised:December 19, 2011 |
| Key Words:
planar graph linear coloring maximum degree.
|
| Fund Project:Supported by the National Natural Science Foundation of China (Grant No.11071223), the Natural Science Foundation of Zhejiang Province (Grant No.Z6090150) and Research Project of Zhejiang Educational Committee (Grant No.Y201121311). |
|
| Hits: 3142 |
| Download times: 2599 |
| Abstract: |
| A linear coloring of a graph $G$ is a proper vertex coloring such that 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 $G$ is the smallest number of colors in a linear coloring of $G$. In this paper, we prove that every planar graph $G$ with maximum degree $5$ is 11-linear-colorable. |
| Citation: |
| DOI:10.3770/j.issn:2095-2651.2012.06.002 |
| View Full Text View/Add Comment |
