|
| 摘要: |
| 图G的一个正常着色满足着任意两种颜色的顶点集合导出的子图是一些点不交的路的并，则称这个正常着色为图的线性着色。图G的线性着色是指G的所有线性着色中所用的最少颜色的个数。研究了平面图的线性着色，对于最大度Δ为偶数的平面图G，证明了lc(G)≤Δ（G）+14 |
| 关键词: 平面图 线性着色 线性色数 最大度 |
| DOI： |
| 分类号: |
| 基金项目: |
|
| Linear Coloring of Planar Graphs |
|
JU Ping
|
| Abstract: |
| A proper coloring of gragh G meets the set of the vertices of any two colors to induce sub-graph which is the number of disjoint paths and this proper coloring is referred to linear coloring.The number of linear coloring of the graph Gindicates the number of minimum colors in all linear coloring of thr graph G. This paper studies the linear coloring of planar graphs and proves lc(G)≤Δ（G）+14 for the planar graphs with maximum degree Δ being even number. |
| Key words: planar graph linear coloring linear chromatic number maximum degree |
