Planar graph

Combinatorics

Discrete mathematics

Edge coloring

Graph

Mathematical analysis

Graph power

Fractional coloring

Generalization

List coloring

Line graph

Signed graph

Mathematics

Graph coloring

Discrete Mathematics

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 Ck is 4-choosable. Furthermore, Jin et al. (2016) showed that for each k∈{3,4,5,6}, every signed planar graph without Ck is signed 4-choosable. In this paper, we show that for each k∈{3,4,5,6}, every planar graph without Ck is 4-DP-colorable, which is an extension of the above results.

A sufficient condition for DP-4-colorability