pith. sign in

arxiv: 1905.02123 · v1 · pith:YY45BW42new · submitted 2019-05-06 · 💻 cs.DM · math.CO

Partitioning sparse graphs into an independent set and a graph with bounded size components

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

We study the problem of partitioning the vertex set of a given graph so that each part induces a graph with components of bounded order; we are also interested in restricting these components to be paths. In particular, we say a graph $G$ admits an $({\cal I}, {\cal O}_k)$-partition if its vertex set can be partitioned into an independent set and a set that induces a graph with components of order at most $k$. We prove that every graph $G$ with $\operatorname{mad}(G)<\frac 52$ admits an $({\cal I}, {\cal O}_3)$-partition. This implies that every planar graph with girth at least $10$ can be partitioned into an independent set and a set that induces a graph whose components are paths of order at most 3. We also prove that every graph $G$ with $\operatorname{mad}(G) < \frac{8k}{3k+1} = \frac{8}{3}\left( 1 - \frac{1}{3k+1} \right)$ admits an $({\cal I}, {\cal O}_k)$-partition. This implies that every planar graph with girth at least $9$ can be partitioned into an independent set and a set that induces a graph whose components are paths of order at most 9.

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.