Premium
Structural theorem on plane graphs with application to the entire coloring number
Author(s) -
Borodin Oleg V.
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199611)23:3<233::aid-jgt3>3.0.co;2-t
Subject(s) - combinatorics , mathematics , conjecture , plane (geometry) , graph , discrete mathematics , brooks' theorem , colored , 1 planar graph , chordal graph , geometry , materials science , composite material
In 1973, Kronk and Mitchem ( Discrete Math. (5) 255–260) conjectured that the vertices, edges and faces of each plane graph G may be colored with D ( G ) + 4 colors, where D ( G ) is the maximum degree of G, so that any two adjacent or incident elements receive distinct colors. They succeeded in verifying this for D ( G ) = 3. A structural theorem on plane graphs is proved in the present paper which implies the validity of this conjecture for all D ( G ) ≥ 7. © 1996 John Wiley & Sons, Inc.