Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.