Premium
Planar graphs without 4‐cycles adjacent to 3‐cycles are list vertex 2‐arborable
Author(s) -
Borodin Oleg V.,
Ivanova Anna O.
Publication year - 2009
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20394
Subject(s) - planar graph , combinatorics , degeneracy (biology) , mathematics , vertex (graph theory) , outerplanar graph , planar straight line graph , 1 planar graph , planar , book embedding , graph , discrete mathematics , pathwidth , chordal graph , computer science , line graph , bioinformatics , biology , computer graphics (images)
It is known that not all planar graphs are 4‐choosable; neither all of them are vertex 2‐arborable. However, planar graphs without 4‐cycles and even those without 4‐cycles adjacent to 3‐cycles are known to be 4‐choosable. We extend this last result in terms of covering the vertices of a graph by induced subgraphs of variable degeneracy. In particular, we prove that every planar graph without 4‐cycles adjacent to 3‐cycles can be covered by two induced forests. © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 234–240, 2009