Relaxed DP-Coloring and another Generalization of DP-Coloring on Planar Graphs without 4-Cycles and 7-Cycles

Abstract

DP-coloring is generalized via relaxed coloring and variable degeneracy in [P. Sittitrai and K. Nakprasit, Su cient conditions on planar graphs to have a relaxed DP-3-coloring, Graphs Combin. 35 (2019) 837–845], [K.M. Nakprasit and K. Nakprasit, A generalization of some results on list coloring and DP-coloring, Graphs Combin. 36 (2020) 1189–1201] and [P. Sittitrai and K. Nakprasit, An analogue of DP-coloring for variable degeneracy and its applications, Discuss. Math. Graph Theory]. In this work, we introduce another concept that includes two previous generalizations. We demonstrate its application on planar graphs without 4-cycles and 7-cycles. One implication is that the vertex set of every planar graph without 4-cycles and 7-cycles can be partitioned into three sets in which each of them induces a linear forest and one of them is an independent set. Additionally, we show that every planar graph without 4-cycles and 7-cycles is DP-(1, 1, 1)-colorable. This generalizes a result of Lih et al. [A note on list improper coloring planar graphs, Appl. Math. Lett. 14 (2001) 269–273] that every planar graph without 4-cycles and 7-cycles is (3, 1)*-choosable.

Keywords

• relaxed dp-colorings
• variable degeneracy
• planar graphs
• discharging
• 05c10
• 05c15