Planar graphs without 4‐cycles adjacent to 3‐cycles are list vertex 2‐arborable |
| |
Authors: | Oleg V Borodin Anna O Ivanova |
| |
Institution: | 1. Institute of Mathematics Siberian Branch of the Russian Academy of Sciences Novosibirsk, 630090, Russia;2. Yakutsk State University Yakutsk, 677000, Russia |
| |
Abstract: | 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 |
| |
Keywords: | graph covering induced subgraphs list coloring point arboricity |
|
|