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

Abstract

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

14 pages. This is an updated version of a submission. In this version, Theorem 1.3 is stronger: instead of $d_0\ge 4$ in the submission, we have $d_0\ge 3$ in this version