Planar graphs without pairwise adjacent 3-,4-,5-, and 6-cycle are\n 4-choosable

2018/12/24 by Pongpat Sittitrai, Sittitrai, Pongpat, Kittikorn Nakprasit +1
Computer Science · Engineering · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1812.10473

openalex publication_date 2018/12/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Xu and Wu proved that if every 5-cycle of a planar graph G is not\nsimultaneously adjacent to 3-cycles and 4-cycles, then G is 4-choosable. In\nthis paper, we improve this result as follows. If G is a planar graph without\npairwise adjacent 3-,4-,5-, and 6-cycle, then G is 4-choosable.\n

Related

• Sufficient conditions on cycles that make planar graphs 4-choosable
• Some conditions on 5-cycles that make planar graphs 4-choosable
• 4-choosability of planar graphs with 4-cycles far apart via the Combinatorial Nullstellensatz
• Acyclic 4‐Choosability of Planar Graphs with No 4‐ and 5‐Cycles
• Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable