| 最大度为7 且不含带弦5- 圈的平面图是8- 全可染的 |
| |
| 引用本文： | 王应前,孙强,陶鑫,沈岚.最大度为7 且不含带弦5- 圈的平面图是8- 全可染的[J].中国科学:数学,2011,41(1):95-104. |
| |
| 作者姓名： | 王应前 孙强 陶鑫 沈岚 |
| |
| 作者单位： | 浙江师范大学数理与信息工程学院, 金华 321004 |
| |
| 基金项目： | 浙江省自然科学基金(批准号：Y6090699)、国家自然科学基金(批准号: 10971198) 和浙江省创新团队(批准号: T200905) 资助 项目 |
| |
| 摘 要： | 若能用k种颜色给图的顶点和边同时进行染色使得相邻或相关联的元素(顶点或边) 染不同的色, 则称这个图是k- 全可染的. 显然, 给最大度为Δ的图进行全染色, 至少要用Δ + 1 种不同的色.本文证明最大度为7 且不含带弦5- 圈的平面图是8- 全可染的. 这一结果进一步拓广了(Δ+1)- 全可染图类.
|
| 关 键 词： | 平面图 全染色 最大度 带弦5- 圈 |
| 收稿时间： | 2009-06-16 |
| 修稿时间： | 2010-11-19 |
Plane graphs with maximum degree 7 and without 5-cycles with chords are 8-totally-colorable |
| |
| WANG YingQian,SUN Qiang,TAO Xin & SHEN Lan.Plane graphs with maximum degree 7 and without 5-cycles with chords are 8-totally-colorable[J].Scientia Sinica Mathemation,2011,41(1):95-104. |
| |
| Authors: | WANG YingQian SUN Qiang TAO Xin & SHEN Lan |
| |
| Institution: | WANG YingQian,SUN Qiang,TAO Xin & SHEN Lan |
| |
| Abstract: | Let G = (V,E) be a graph with the set of vertices V and the set of edges E. If one can use k colors to color the elements in V ∪ E such that any pair of adjacent or incident elements receive distinct colors, then G is said to be k-totally-colorable. Clearly, at least Δ + 1 colors are needed to color a graph totally, where Δ is the maximum degree of G. It is known that the plane graphs with maximum degree Δ > 8 and without 5-cycles with chords are (Δ + 1)-totally-colorable. In this paper, we prove that the plane graphs with maximum degree 7 and without 5-cycles with chords are 8-totally-colorable. |
| |
| Keywords: | plane graphzz total coloringzz maximum degreezz 5-cycleszz chordszz |
| 本文献已被 CNKI 维普 等数据库收录！ |
| 点击此处可从《中国科学:数学》浏览原始摘要信息 |
| 点击此处可从《中国科学:数学》下载免费的PDF全文 |
