A Sufficient condition for DP-4-colorability

2017/09/28 by Seog‐Jin Kim, Kenta Ozeki, Kim, Seog-Jin +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.1709.09809

openalex publication_date 2017/09/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

DP-coloring of a simple graph is a generalization of list coloring, and also a generalization of signed coloring of signed graphs. It is known that for each k ∈ \3, 4, 5, 6\, every planar graph without C_k is 4-choosable. Furthermore, Jin, Kang, and Steffen \citeJKS showed that for each k ∈ \3, 4, 5, 6\, every signed planar graph without C_k is signed 4-choosable. In this paper, we show that for each k ∈ \3, 4, 5, 6\, every planar graph without C_k is 4-DP-colorable, which is an extension of the above results.

Related

• 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-4-colorability of two classes of planar graphs
• Sufficient conditions on planar graphs to have a relaxed DP-3-colorability
• Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable
• Planar graphs without 7-cycles and butterflies are DP-4-colorable