✦ LIBER ✦
Planar graphs without 4-cycles adjacent to 3-cycles are list vertex 2-arborable
✍ Scribed by Oleg V. Borodin; Anna O. Ivanova
- Publisher
- John Wiley and Sons
- Year
- 2009
- Tongue
- English
- Weight
- 80 KB
- Volume
- 62
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
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