| 王侃,王维凡.最大度为5的平面图是11-线性可染的[J].数学研究及应用,2012,32(6):641~653 |
| 最大度为5的平面图是11-线性可染的 |
| Plane Graphs with Maximum Degree 5 Are 11-Linear-Colorable |
| 投稿时间：2011-06-21 修订日期：2011-12-19 |
| DOI：10.3770/j.issn:2095-2651.2012.06.002 |
| 中文关键词: 平面图 线性染色 最大度. |
| 英文关键词:planar graph linear coloring maximum degree. |
| 基金项目:国家自然科学基金资助项目(Grant No.11071223),浙江省自然科学基金重点项目(Grant No.Z6090150),浙江省教育厅科研项目(Grant No.Y201121311). |
|
| 摘要点击次数: 3143 |
| 全文下载次数: 2599 |
| 中文摘要: |
| 如果图 $G$的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图 $G$ 的线性染色. 图 $G$ 的线性色数用 lc$(G)$表示, 是指 $G$ 的所有线性染色中所用的最少颜色的个数. 证明了: 最大度为 5 的平面图是 $11$-线性可染的. |
| 英文摘要: |
| 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. |
| 查看全文 查看/发表评论 下载PDF阅读器 |
