On the 7 Total Colorability of Planar Graphs with Maximum Degree 6 and without 4-cycles

摘要

Vizing and Behzad independently conjectured that every graph is (Delta + 2)-totally-colorable, where Delta denotes the maximum degree of G. This conjecture has not been settled yet even for planar graphs. The only open case is Delta = 6. It is known that planar graphs with Delta a parts per thousand yen 9 are (Delta + 1)-totally-colorable. We conjecture that planar graphs with 4 a parts per thousand currency sign Delta a parts per thousand currency sign 8 are also (Delta + 1)-totally-colorable. In addition to some known results supporting this conjecture, we prove that planar graphs with Delta = 6 and without 4-cycles are 7-totally-colorable.