DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

P. Sittitrai, K. Nakprasit

Title:

An analogue of DP-coloring for variable degeneracy and its applications

Source:

Discussiones Mathematicae Graph Theory

Received: 2018-08-22, Revised: 2019-06-12, Accepted: 2019-06-30, https://doi.org/10.7151/dmgt.2238

Abstract:

A graph $G$ is list vertex $k$-arborable if for every $k$-assignment $L,$ one can choose $f(v)\in L(v)$ for each vertex $v$ so that vertices with the same color induce a forest. In \cite{listnoC3adjC4}, Borodin and Ivanova proved that every planar graph without $4$-cycles adjacent to $3$-cycles is list vertex $2$-arborable. In fact, they proved a more general result in terms of variable degeneracy. Inspired by these results and DP-coloring which is a generalization of list coloring and has become a widely studied topic, we introduce a generalization on variable degeneracy including list vertex arboricity. We use this notion to extend a general result by Borodin and Ivanova. Not only this theorem implies results about planar graphs without $4$-cycles adjacent to $3$-cycle by Borodin and Ivanova, it also implies other results including a result by Kim and Yu [S.-J. Kim and X. Yu, Planar graphs without $4$-cycles adjacent to triangles are DP-$4$-colorable, Graphs Combin. 35 (2019) 707–718] that every planar graph without $4$-cycles adjacent to $3$-cycles is DP-$4$-colorable.

Keywords:

DP-colorings, arboricity colorings, planar graphs

PDF
Close