DP-4-colorability of two classes of planar graphs

2018/11/07 by Lily Chen, Chen, Lily, Runrun Liu +7
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.1811.02920

openalex publication_date 2018/11/07 · 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 recently by Dvořák and Postle (2017). In this paper, we prove that every planar graph G without 4-cycles adjacent to k-cycles is DP-4-colorable for k=5 and 6. As a consequence, we obtain two new classes of 4-choosable planar graphs. We use identification of verticec in the proof, and actually prove stronger statements that every pre-coloring of some short cycles can be extended to the whole graph.

Related

• Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable
• Planar graphs without 7-cycles and butterflies are DP-4-colorable
• 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-coloring for planar graphs of diameter two
• A Sufficient condition for DP-4-colorability