CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location:  PublicationsjournalsCMB
Publications        
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, 05C10 show english descriptions Coloring of graphs and hypergraphs
Planar graphs; geometric and topological aspects of graph theory [See also 57M15, 57M25]
05C15 - Coloring of graphs and hypergraphs
05C10 - Planar graphs; geometric and topological aspects of graph theory [See also 57M15, 57M25]
 

© Canadian Mathematical Society, 2014 : https://cms.math.ca/