王侃,王维凡.最大度为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).
作者单位
王侃 浙江师范大学数理与信息工程学院, 浙江 金华 321004 
王维凡 浙江师范大学数理与信息工程学院, 浙江 金华 321004 
摘要点击次数: 1813
全文下载次数: 1804
中文摘要:
      如果图 $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阅读器