Every planar graph without adjacent short cycles is 3-colorable

2010/04/05 by Tao Wang, Wang, Tao
Computer Science · Engineering · Mathematics · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO #msc:05C15

paper · pdf · doi:10.48550/arxiv.1004.0582

14 pages, 16 figures

arxiv created 2010/04/05 · openalex publication_date 2010/04/05 · arxiv updated 2010/04/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Two cycles are \em adjacent if they have an edge in common. Suppose that G is a planar graph, for any two adjacent cycles C₁ and C₂, we have |C₁| + |C₂| ≥ 11, in particular, when |C₁| = 5, |C₂| ≥ 7. We show that the graph G is 3-colorable.

Related

• A comment to: On 3-colorable planar graphs without short cycles
• 3-choosability of planar graphs with (<=4)-cycles far apart
• Planar graphs without cycles of length 4 or 5 are (11:3)-colorable
• Planar graphs without 5^--cycles at distance less than 3 are (I, F)-colorable
• Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable