Partitioning Sparse Graphs into an Independent Set and a Forest of Bounded Degree
Abstract
An $(I,F_d)$-partition of a graph is a partition of the vertices of the graph into two sets $I$ and $F$, such that $I$ is an independent set and $F$ induces a forest of maximum degree at most $d$. We show that for all $M < 3$ and $d>\frac2{3 −M}−2$, if a graph has maximum average degree less than $M$, then it has an $(I,F_d)$-partition. Additionally, we prove that for all $\frac83 \le M < 3$ and $d>\frac1{3−M}$, if a graph has maximum average degree less than $M$ then it has an $(I,F_d)$-partition. It follows that planar graphs with girth at least $7$ (resp. $8$, $10$) admit an $(I,F_5)$-partition (resp. $(I,F_3)$-partition, $(I,F_2)$-partition).
Origin | Files produced by the author(s) |
---|
Loading...