location:  Publications → journals → CMB
Abstract view

On the Entire Coloring Conjecture

Published:2000-03-01
Printed: Mar 2000
• Daniel P. Sanders
• Yue Zhao
 Format: HTML LaTeX MathJax PDF PostScript

Abstract

The Four Color Theorem says that the faces (or vertices) of a plane graph may be colored with four colors. Vizing's Theorem says that the edges of a graph with maximum degree $\Delta$ may be colored with $\Delta+1$ colors. In 1972, Kronk and Mitchem conjectured that the vertices, edges, and faces of a plane graph may be simultaneously colored with $\Delta+4$ colors. In this article, we give a simple proof that the conjecture is true if $\Delta \geq 6$.
 MSC Classifications: 05C15 - Coloring of graphs and hypergraphs 05C10 - Planar graphs; geometric and topological aspects of graph theory [See also 57M15, 57M25]