Planar graphs without 7-cycles and butterflies are DP-4-colorable

2019/07/15 by Seog‐Jin Kim, Runrun Liu, Kim, Seog-Jin +3
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.1907.06789

openalex publication_date 2019/07/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

DP-coloring (also known as correspondence coloring) is a generalization of list coloring, introduced by Dvořák and Postle in 2017. It is well-known that there are non-4-choosable planar graphs. Much attention has recently been put on sufficient conditions for planar graphs to be DP-4-colorable. In particular, for each k ∈ \3, 4, 5, 6\, every planar graph without k-cycles is DP-4-colorable. In this paper, we prove that every planar graph without 7-cycles and butterflies is DP-4-colorable. Our proof can be easily modified to prove other sufficient conditions that forbid clusters formed by many triangles.

Related

• Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable
• DP-4-colorability of two classes of planar graphs
• 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
• Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable
• DP-3-coloring of planar graphs without 4,9-cycles and two cycles from \5,6,7,8\