On vertex types and cyclic colourings of 3-connected plane graphs

摘要

We prove a structural theorem of Lebesgue's type concerning the existence of certain types of vertices in 3-connected plane graphs. This theorem is then applied to the proof such that the cyclic chromatic number χ_c(G) ≤ k + 2 for k = max{40, Δ~*(G)}, where Δ~*(G) denotes the size of the largest face of G. This confirms a conjecture by Plummer and Toft for Δ~*(G) ≥ 40.