Skip to main content
Article
DP-4-colorability of two classes of planar graphs
Discrete Mathematics
  • Lily Chen
  • Runrun Liu
  • G. Yu
  • Ren Zhao
  • Xiangqian Zhou, Wright State University - Main Campus
Document Type
Article
Publication Date
11-1-2019
Abstract

DP-coloring (also known as correspondence coloring) is a generalization of list coloring introduced by Dvořák and Postle in 2017. In this paper, we prove that every planar graph 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 vertices in the proof, and actually prove stronger statements that every pre-coloring of some short cycles can be extended to the whole graph.

DOI
10.1016/j.disc.2019.05.032
Citation Information
Lily Chen, Runrun Liu, G. Yu, Ren Zhao, et al.. "DP-4-colorability of two classes of planar graphs" Discrete Mathematics Vol. 342 Iss. 11 (2019) p. 2984 - 2993 ISSN: 0012365X
Available at: http://works.bepress.com/xiangqian_zhou/9/