(I,F)-partition of planar graphs without cycles of length 4, 6, or 9

Abstract

A graph $G$ is $(I,F)$-partitionable if its vertex set can be partitioned into two parts such that one part is an independent set, and the other induces a forest. In this paper, we prove that every planar graph without cycles of length $4,6,9$ is $(I,F)$-partitionable.

9 pages, 5 figures