| On total chromatic number of planar graphs without 4-cycles |
| |
| 作者姓名： | Min-le SHANGGUAN |
| |
| 作者单位： | College of |
| |
| 摘 要： | Let G be a simple graph with maximum degree A(G) and total chromatic number Xve(G). Vizing conjectured thatΔ(G) 1≤Xve(G)≤Δ(G) 2 (Total Chromatic Conjecture). Even for planar graphs, this conjecture has not been settled yet. The unsettled difficult case for planar graphs isΔ(G) = 6. This paper shows that if G is a simple planar graph with maximum degree 6 and without 4-cycles, then Xve(G)≤8. Together with the previous results on this topic, this shows that every simple planar graph without 4-cycles satisfies the Total Chromatic Conjecture.
|
| 收稿时间： | 11 January 2005 |
| 修稿时间： | 10 July 2006 |
On total chromatic number of planar graphs without 4-cycles |
| |
| Min-le SHANGGUAN.On total chromatic number of planar graphs without 4-cycles[J].Science in China(Mathematics),2007,50(1):81-86. |
| |
| Authors: | Ying-qian Wang Min-le Shangguan Qiao Li |
| |
| Institution: | 1. College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua 321004,China
2. Department of Applied Mathematics, Shanghai Jiaotong University, Shanghai 200030, China |
| |
| Abstract: | Let G be a simple graph with maximum degree Δ(G) and total chromatic number x
ve
(G). Vizing conjectured that Δ(G) + 1 ⩽ X
ve
(G) ⩽ δ(G) + 2 (Total Chromatic Conjecture). Even for planar graphs, this conjecture has not been settled yet. The unsettled difficult
case for planar graphs is Δ(G) = 6. This paper shows that if G is a simple planar graph with maximum degree 6 and without 4-cycles, then x
ve
(G) ⩽ 8. Together with the previous results on this topic, this shows that every simple planar graph without 4-cycles satisfies
the Total Chromatic Conjecture.
This work was partially supported by the National Natural Science Foundation of China (Grant No. 10471131) |
| |
| Keywords: | total chromatic number planar graph F5-subgraph |
| 本文献已被 CNKI 万方数据 SpringerLink 等数据库收录！ |
