An analogue of DP-coloring for variable degeneracy and its applications
Author(s) -
Sittitrai Pongpat,
Nakprasit Kittikorn
Publication year - 2019
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.2238
Subject(s) - mathematics , degeneracy (biology) , combinatorics , variable (mathematics) , mathematical analysis , bioinformatics , biology
In \cite{listnoC3adjC4}), Borodin and Ivanova proved that every planar graph without $4$-cycles adjacent to $3$-cycle is list vertex-$2$-aborable. In fact, they proved a more general result. Inspired by these results and DP-coloring which becomes 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 that this theorem implies results about planar graphs without $4$-cycles adjacent to $3$-cycle by Borodin and Ivanova, it implies many other results including a result by Kim and Yu \cite{KimY} that every planar graph without $4$-cycles adjacent to $3$-cycle is DP-$4$-colorable.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom