A note on improper DP-colouring of planar graphs. Issue 2 (3rd April 2021)

• Record Type: Journal Article
• Authors: Cai, Hongyan; Sun, Qiang
• Is Part Of: International journal of computer mathematics. Volume 6:Issue 2(2021)
• Page Start: 159
• Page End: 166
• Publication Date: 2021-04-03
• Subjects: DP-colouring -- planar graph -- cycles -- list colouring -- improper colouring; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2021.1872707
• Languages: English
• ISSNs: 2379-9927

Abstract

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 ) ∗ -colouring to generalize ( k, d ) ∗ -colouring and ( k, d ) ∗ -choosability. They proved that every planar graph G without { 4, 6 } -cycles is DP- ( 3, 1 ) ∗ -colourable. In this note, we show the following results:(1) Every planar graph G without { 4, 5, 7 } -cycles is DP- ( 3, 1 ) ∗ -colourable; (2) Every planar graph G without { 4, 5, 9 } -cycles is DP- ( 3, 1 ) ∗ -colourable; (3) Every planar graph G without { 4, 8 } -cycles is DP- ( 3, 1 ) ∗ -colourable.