2006/07/03 by Fédéric Havet, Havet, Fédéric, Jean‐Sébastien Sereni +3
Computer Science · Engineering · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.cs/0607008
openalex publication_date 2006/07/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A plane graph is l-facially k-colourable if its vertices can be coloured with k colours such that any two distinct vertices on a facial segment of length at most l are coloured differently. We prove that every plane graph is 3-facially 11-colourable. As a consequence, we derive that every 2-connected plane graph with maximum face-size at most 7 is cyclically 11-colourable. These two bounds are for one off from those that are proposed by the (3l+1)-Conjecture and the Cyclic Conjecture.