pith. sign in

arxiv: 1606.04394 · v1 · pith:5Q2X5VXBnew · submitted 2016-06-14 · 💻 cs.DM · math.CO

Partitioning sparse graphs into an independent set and a forest of bounded degree

classification 💻 cs.DM math.CO
keywords degreegraphpartitionfracmaximumaverageforestindependent
0
0 comments X
read the original abstract

An $({\cal I},{\cal 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 \ge \frac{2}{3-M} - 2$, if a graph has maximum average degree less than $M$, then it has an $({\cal I},{\cal F}_d)$-partition. Additionally, we prove that for all $\frac{8}{3} \le M < 3$ and $d \ge \frac{1}{3-M}$, if a graph has maximum average degree less than $M$ then it has an $({\cal I},{\cal F}_d)$-partition.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.