Premium
Plane Graphs with Maximum Degree Δ ≥ 8 Are Entirely ( Δ + 3 ) ‐Colorable
Author(s) -
Wang Yingqian,
Mao Xianghua,
Miao Zhengke
Publication year - 2013
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/jgt.21676
Subject(s) - combinatorics , mathematics , conjecture , graph , simple graph , plane (geometry) , planar graph , simple (philosophy) , degree (music) , discrete mathematics , geometry , physics , philosophy , epistemology , acoustics
Let G = ( V , E , F ) be a plane graph with the sets of vertices, edges, and faces V , E , and F , respectively. If one can color all elements in V ∪ E ∪ F using k colors so that any two adjacent or incident elements receive distinct colors, then G is said to be entirely k ‐colorable. Kronk and Mitchem [Discrete Math 5 (1973) 253‐260] conjectured that every plane graph with maximum degree Δ is entirely ( Δ + 4 ) ‐colorable. This conjecture has now been settled in Wang and Zhu (J Combin Theory Ser B 101 (2011) 490–501), where the authors asked: is every simple plane graph G ≠ K 4entirely ( Δ + 3 ) ‐colorable? In this article, we prove that every simple plane graph with Δ ≥ 8 is entirely ( Δ + 3 ) ‐colorable, and conjecture that every simple plane graph, except the tetrahedron, is entirely ( Δ + 3 ) ‐colorable.