1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ There might be an uncolored node, some of whose neighbors are already colored. $\endgroup$ – Yuval Filmus Jan 15 '18 at 10:04
  • $\begingroup$ Yes, edited my algorithm description $\endgroup$ – shaqed Jan 15 '18 at 10:07
  • $\begingroup$ 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? $\endgroup$ – Yuval Filmus Jan 15 '18 at 10:07
  • $\begingroup$ 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? $\endgroup$ – Yuval Filmus Jan 15 '18 at 10:08
  • $\begingroup$ 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 $\endgroup$ – shaqed Jan 15 '18 at 10:09
2
$\begingroup$

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.

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