| 围长至少为5的平面图的线性染色 |
| |
| 引用本文： | 王侃,王维凡.围长至少为5的平面图的线性染色[J].数学研究,2011,44(1):76-85. |
| |
| 作者姓名： | 王侃 王维凡 |
| |
| 作者单位： | 浙江师范大学数理与信息工程学院,浙江,金华,321004 |
| |
| 基金项目： | 国家自然科学基金资助项目，浙江省自然科学基金重点项目 |
| |
| 摘 要： | 如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc(G)表示,是指G的所有线性染色中所用的最少颜色的个数本文证明了对于每一个最大度为△(G)且围长至少为5的平面图G有lc(G)≤△(G)/2]+5,并且当△(G)∈{7,8,…,14...
|
| 关 键 词： | 平面图 线性染色 围长 最大度 |
Linear Coloring of Planar Graphs with Girth at Least Five |
| |
| Wang Kan,Wang Weifan.Linear Coloring of Planar Graphs with Girth at Least Five[J].Journal of Mathematical Study,2011,44(1):76-85. |
| |
| Authors: | Wang Kan Wang Weifan |
| |
| Institution: | Wang Kan Wang Weifan (College of Mathematics,Physics and Information Engineering,Zhejiang Normal University,Jinhua Zhejiang 321004) |
| |
| Abstract: | A linear coloring 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 the graph G is the smallest number of colors in a linear coloring of G.In this paper,it is proved that every plane graph G with maximum degreeΔ（G） and girth at least five has lc（G）≤（Δ（G））/2]＋5.and ifΔ（G） {7.8.….14}.then lc（G）≤（Δ（G））/2]＋4. |
| |
| Keywords: | Planar graph Linear coloring Girth Maximum degree |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
