Partition of a graph into subgraphs with small maximum degree

Question

Denote the maximum degree of an undirected graph $G=(V,E)$ by $\Delta$. That is, $\Delta = \max_{v\in V} \deg(v)$. I'm looking for a way to divide $G$ into two separate induced subgraphs $G_1=(V_1,E_1),\,\,G_2=(V_2,E_2)$ such that:

• $V=V_1\dot{\cup} V_2$ (That is, $V$ is the union of $V_1, \,V_2$ and they are disjoint).
• $E_i$ are the induced edges from $G$ with both vertices being from $V_i$ (That is, $E_i=\{ (u,v) \, | \,\,u,v\in V_i \wedge (u,v)\in E\} $).

(Note that some edges will be neither in $E_1$ nor $E_2$, being cross edges.)

and:

• The maximum degree, $\Delta_i$ (of $G_i$) is bounded by $\frac{\Delta}{2}$, or by another constant $c<1$: $\,\,\,\Delta_i \leq c\cdot \Delta$.

If I divide the vertices arbitrary, then I have no bound on $\Delta_i$ and I cannot guarantee it will even get smaller (it may remain $\Delta$). Is there a way to divide the graph while maintaining this upper bound on $\Delta_i$?

Additionally, if the answer to the above is positive, I would like to expand this idea to $G_1, \dots ,G_k$ where $k\in\mathbb{N}$, such that each $\Delta_k$ will have a tighter upper bound.

Answer 1

Yes, every graph $G$ with maximum degree $\Delta$ can be partitioned into $k$ sets $X_1, \dots, X_k$ such that the maximum degree of $G[X_i]$ is at most $\lfloor \Delta / k \rfloor$ for all $i$. This bound is best possible (consider the complete graphs $K_n$).

Proof. Given an arbitrary partition of $V(G)$, call an edge monochromatic, if both of its ends are in one set of the partition. The required partition is obtained by choosing a partition $X_1, \dots, X_k$ that minimizes the number of monochromatic edges. Suppose not and assume $v \in X_i$ has more than $\lfloor \Delta / k \rfloor$ neighbours in $X_i$. By the Pigeonhole Principle, there must be some $X_j \neq X_i$ with at most $\lfloor \Delta / k \rfloor$ neighbours of $v$. Moving $v$ from $X_i$ to $X_j$, decreases the number of monochromatic edges, which is a contradiction.