Defective 2-colorings of planar graphs without 4-cycles and 5-cycles

2016/11/30 by Pongpat Sittitrai, Sittitrai, Pongpat, Kittikorn Nakprasit +1
Computer Science · Engineering · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #G.2.2 #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1611.10239

openalex publication_date 2016/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let G be a graph without 4-cycles and 5-cycles. We show that the problem to determine whether G is (0,k)-colorable is NP-complete for each positive integer k. Moreover, we construct non-(1,k)-colorable planar graphs without 4-cycles and 5-cycles for each positive integer k. Finally, we prove that G is (d₁,d₂)-colorable where (d₁,d₂)=(4,4), (3,5), and (2,9).

Related

• (2,4)-Colorability of Planar Graphs Excluding 3-, 4-, and 6-Cycles
• (1,0,0)-colorability of planar graphs without cycles of length 4 or 6
• Near-colorings: non-colorable graphs and NP-completeness
• Planar graphs having no cycle of length 4, 6 or 8 are DP-3-colorable
• Planar graphs without cycles of length 4 or 5 are (7m:2m)-DP-colorable