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

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\in \{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.

11 pages, 6 figures