3
$\begingroup$

Given an undirected graph I'd like to color each node either black or red such that at most half of every node's neighbors have the same color as the node itself. As a first step, I'd like to show that this is always possible.

I believe this problem is the essence of the math quiz #2 in Communications of the ACM 02/2011 where I found it, so you might consider this a homework-like question. The quiz deals with partitions but I found it more natural to formulate the problem as a graph-coloring problem.

Coming from computer science with some math interest I'm not sure how to approach this and would be glad about some hints. One observation is that any node of degree 1 forces its neighbor to be of the opposite color. This could lead to a constructive proof (or a greedy algorithm) that provides a coloring. However, an existence proof would be also interesting.

2 Answers 2

4

Hint: Start with a random colouring and try to increase the number of edges which have differently coloured endpoints.

Spoiler:

Pick a node which has more than half of it's neighbour of the same colour as itself and flip it's colour. Now show that, as a result, the number of edges with different coloured endpoints increases by at least 1. Repeat.

2

Perhaps related is the following well-known riddle: At each step, all the nodes (simultaneously) choose their color as the majority color of their neighbors (or black in case of a tie). Show that this process converges to either a fixed point or a $2$-cycle.

This charming riddle is solved by comparing the state at time $t$ to the state at time $t+2$, and using a potential function. This solution was published, and generalized in a sequence of papers.

In your case, you want to take the anti-majority. Perhaps the same techniques work, though I'm not sure how a $2$-cycle will help you.