Graph coloring where a maximum of 2 neighboring nodes can have the same color.

Question

We are given a graph where each node can have at most 3 edges. We want to color this graph into 2 colors such that each node can have at most one neighbor with the same color as itself.

How to prove that given a graph that follows the above structure, there exists a solution? What are the conditions for that solution? (does it always exist), and how can we find one coloring solution that satisfies the above constraints.

Answer 1

A different perspective on this is that you are looking for an external or unfriendly partition of your (sub-cubic) graph $G=(V,E)$. I.e., a partition $\{A,B\}$ of $V$ so that each vertex of $A$ has at least as many neighbours in $B$ as it does in $A$, and each vertex of $B$ has at least as many neighbours in $A$ as it does in $B$.

Every graph has an external partition, and Paul Erdos came up with a nice way to find them. To carry out this process, we'll need some terms.

If $G=(V,E)$ is your graph, and $\{A,B\}$ is a partition of $V$ (i.e., $V=A\cup B$, and $A$ and $B$ are not empty, and $A\cap B = \emptyset$), then let $e(A,B)$ be the number of edges with one vertex in $A$ and one vertex in $B$. Further, let $d_A(u)$ be the number of vertices in $A$ that $u$ is adjacent to, and $d_B(u)$ the number of vertices in $B$ that $u$ is adjacent to.

---

Erdos's observation was that a partition $\{X,Y\}$ that maximised $e(X,Y)$ must be an external partition! For if it wasn't an external partition, you could take a vertex $u$ in $X$ with $d_X(u) > d_Y(u)$ and move it from $X$ to $Y$. But then we'd have $e(X-u, Y+u) > e(X,Y)$, contradicting the fact that $\{X,Y\}$ maximised the number $e(X,Y)$ of edges across it. It's also possible you'd have $u$ in $Y$ with $d_X(u) < d_Y(u)$, in which case you'd move it over to $X$.

This (roughly, there's some subtlety about maximality I'm glossing over) gives us a nice recipe for finding such a partition:

1. Find any partition $\{A,B\}$ of your graph's vertex set.
2. If your partition is already external, great, you are done! If not, go to 3.
3. If not, then there is a vertex $u$ in $A$ with $d_A(u) > d_B(u)$. Take this vertex $u$, and move it into $B$. You'll now have a new partition with more edges across it: so you'll have $\{A-u, B+u\}$ with $e(A-u, B+u) > e(A,B)$. Alternatively, you'll only be able to find a vertex $v\in B$ with $d_B(v) > d_(v)$, in which case you move the vertex $v$ from $B$ to $A$ and note that $e(A+v, B-v) > e(A,B)$. (See picture below)
4. Repeat steps 2 and 3 until you get an external partition. Since the number of edges across the partition increases every step, and the graph has finitely many edges, this process must eventually terminate.