On total 9-coloring planar graphs of maximum degree seven

✍ Scribed by Sanders, Daniel P.; Zhao, Yue

• Publisher: John Wiley and Sons
• Year: 1999
• Tongue: English
• Weight: 202 KB
• Volume: 31
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199905)31:1<67::aid-jgt6>3.0.co;2-c

✦ Synopsis

Given a graph G, a total k-coloring of G is a simultaneous coloring of the vertices and edges of G with at most k colors. If ∆(G) is the maximum degree of G, then no graph has a total ∆-coloring, but Vizing conjectured that every graph has a total (∆ + 2)-coloring. This Total Coloring Conjecture remains open even for planar graphs. This article proves one of the two remaining planar cases, showing that every planar (and projective) graph with ∆ ≤ 7 has a total 9-coloring by means of the discharging method.