最大度为5的平面图是11-线性可染的

Plane Graphs with Maximum Degree 5 Are 11-Linear-Colorable

中文关键词:  平面图  线性染色  最大度.

英文关键词:planar graph  linear coloring  maximum degree.

中文摘要:

      如果图 $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.