Denote the maximal 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 sub-graphs $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$ neither in $E_2$, being cross edges.)

and:

• The maximal 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 limitation 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,...,G_k$ where $k\in\mathbb{N}$, such that each $\Delta_k$ will have a tighter upper bound.