Destroying Non-Complete Regular Components in Graph Partitions

Abstract

We prove that if $G$ is a graph and $r_1,...,r_k\in {\mathbb{Z}}_{\ge 0}$ such that ${\sum }_{i=1}^k{r}_i\ge \Delta (G)+2-k$ then $V(G)$ can be partitioned into sets $V_1,...,V_k$ such that $\Delta (G[V_i])\le r_i$ and $G[V_i]$ contains no non-complete $r_i$-regular components for each $1\le i\le k$. In particular, the vertex set of any graph $G$ can be partitioned into $\lceil \frac{\Delta (G)+2}{3}\rceil$ sets, each of which induces a disjoint union of triangles and paths.

Cited by in corpus (1)

• A note on vertex partitions