3.8 Article

On total chromatic number of planar graphs without 4-cycles

Journal

SCIENCE IN CHINA SERIES A-MATHEMATICS
Volume 50, Issue 1, Pages 81-86

Publisher

SCIENCE PRESS
DOI: 10.1007/s11434-007-2031-x

Keywords

total chromatic number; planar graph; F-5-subgraph

Ask authors/readers for more resources

Let G be a simple graph with maximum degree A(G) and total chromatic number chi(ve) (G). Vizing conjectured that Delta(G) + 1 <= chi(ve) (G) <= Delta(G) + 2 (Total Chromatic Conjecture). Even for planar graphs, this conjecture has not been settled yet. The unsettled difficult case for planar graphs is Delta(G) = 6. This paper shows that if G is a simple planar graph with maximum degree 6 and without 4-cycles, then chi v(e) (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.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

3.8
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available