# Coloring a cubic-graph with 2 colors

Given a cubic graph, I want to color its vertices in 2 colors (Say A & B).

A vertex is considered "Good" iff the majority of its neighbors is colored differently than that vertex. (For example, vertex colored A has neighbors A B B is considered Good, and a vertex colored A has neighbors A A B is considered "Bad")

I suggest the following algorithm:

• Pick a random uncolored node
• Color it in a way that 2 of its neighbors are X, and the last one is Y (Sometimes of course the neighbors are already colored and we determine from that what color the node needs to be and its neighbors also)
• Color the node Y

Running this algorithm seems to work, but I couldn't find an example that it doesn't. And even worse - I cannot even understand how to even begin the proof that this algorithm is correct (if at all)

I feel like I need to use the fact that this is a cubic-graph. But I cannot seem to understand how would that help me here.

EDIT (Observations):

• It seems that if I get to pick X uncolored nodes, may graph would have at least X "good" nodes (According to the algorithm)
• That X would be at least |V|/4

I want to start by proving that there can be more than |V|/4 "Good" nodes, because in all of my examples there are at least |V|/2 "Good" nodes.

• There might be an uncolored node, some of whose neighbors are already colored. – Yuval Filmus Jan 15 '18 at 10:04
• Yes, edited my algorithm description – shaqed Jan 15 '18 at 10:07
• Are you trying to show that every cubic graph can be colored in such a way that all vertices are good? If so, why use the tags randomized and approximation? – Yuval Filmus Jan 15 '18 at 10:07
• When your algorithm colors a node, it ensures that that node is good, but one of its neighbors could potentially be bad. Have you checked whether this can actually happen? – Yuval Filmus Jan 15 '18 at 10:08
• I'm not trying to show that - I'm trying to create an algorithm to generate the "maximum" number of "good" nodes that I can. Its because I'm not sure that my algorithm is optimal (I'm pretty sure that it's not) I feel like this is an approximation algorithm – shaqed Jan 15 '18 at 10:09

## 1 Answer

A 2-coloring of a cubic graph in which all vertices are good is known as an unfriendly partition. Such a coloring always exists, and the following algorithm finds it:

• Start with an arbitrary coloring, say everything is colored blue.
• While there exists a bad vertex: pick some bad vertex, and flip its color.

Why does the algorithm terminate? Consider the number of monochromatic edges. Flipping the color of a bad vertex decreases the number of monochromatic edges. Since there are $1.5n$ edges, the algorithm terminates after at most $1.5n$ steps.

In fact, the entire algorithm can be implemented in $O(n)$ time, essentially since every step only affects $O(1)$ vertices. The basic idea is to maintain a stack or queue of bad vertices.