1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.