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.
- 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.