Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable

2018/09/04 by Yin, Yuxue, Yu, Gexin
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1809.00925

Abstract

Montassier, Raspaud, and Wang (2006) asked to find the smallest positive integers d₀ and d₁ such that planar graphs without \4,5\-cycles and d^Δ≥ d₀ are 3-choosable and planar graphs without \4,5,6\-cycles and d^Δ≥ d₁ are 3-choosable, where d^Δ is the smallest distance between triangles. They showed that 2≤ d₀≤ 4 and d₁≤ 3. In this paper, we show that the following planar graphs are DP-3-colorable: (1) planar graphs without \4,5\-cycles and d^Δ≥ 3 are DP-3-colorable, and (2) planar graphs without \4,5,6\-cycles and d^Δ≥ 2 are DP-3-colorable. DP-coloring is a generalization of list-coloring, thus as a corollary, d₀≤ 3 and d₁≤ 2. We actually prove stronger statements that each pre-coloring on some cycles can be extended to the whole graph.

Related

• Planar graphs having no cycle of length 4, 6 or 8 are DP-3-colorable
• Every planar graph without adjacent cycles of length at most 8 is 3-choosable
• Every planar graph without i-cycles adjacent simultaneously to\n j-cycles and k-cycles is DP-4-colorable when i,j,k = 3,4,5
• DP-3-coloring of planar graphs without 4,9-cycles and two cycles from \5,6,7,8\
• DP-3-colorability of planar graphs without cycles of length 4, 7 or 9