A note on improper DP-colouring of planar graphs

ABSTRACT

DP-colouring (also known as correspondence colouring), introduced by Dvořák and Postle, is a generalization of list colouring. Many results on list-colouring of graphs, especially of planar graphs, have been extended to the setting of DP-colouring. Recently, Pongpat and Kittikorn [P. Sittitrai and K. Nakprasit, Suffficient conditions on planar graphs to have a relaxed DP-3-colourability, Graphs and Combinatorics 35 (2019), pp. 837–845.] introduced DP-$(k,d{)}^{\ast }$-colouring to generalize $(k,d{)}^{\ast }$-colouring and $(k,d{)}^{\ast }$-choosability. They proved that every planar graph G without $\{4,6\}$-cycles is DP-$(3,1{)}^{\ast }$-colourable. In this note, we show the following results:(1) Every planar graph G without $\{4,5,7\}$-cycles is DP-$(3,1{)}^{\ast }$-colourable; (2) Every planar graph G without $\{4,5,9\}$-cycles is DP-$(3,1{)}^{\ast }$-colourable; (3) Every planar graph G without $\{4,8\}$-cycles is DP-$(3,1{)}^{\ast }$-colourable.

KEYWORDS:

• DP-colouring
• planar graph
• cycles
• list colouring
• improper colouring

Acknowledgments

We are thankful to the referees for their valuable suggestions.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work is supported by National Natural Science Foundation of China (No.11801494), Natural Science Foundation of Jiangsu Province (No.BK20170480).