Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let us relax the coloring a little bit, that is, we allow a small number of adjacent vertices to be assigned the same color. A monochromatic component is defined to be a connected component in the subgraph induced by the set of vertices that receive the same color, and the question is to ask for the minimum number $\lambda$ of colors needed to color a graph such that largest monochromatic component has size no more than $C$.
The traditional coloring can be considered as $[\lambda,1]$-coloring in this setting. Hence to find the minimum number of $\lambda$ is NP-hard for planar graph in general.

My question is, how about $[\lambda,2]$-coloring of planar graphs, or more generally, $[\lambda,C]$-coloring for $C \geq 2$?

This can be viewed as a dual problem of what is studied by Edwards and Farr, where $\lambda$ is fixed, and one is asked to find the minimum size of $C$.

share|cite|improve this question
up vote 3 down vote accepted

2-colorable perfect matching in cubic planar graphs is very similar to your problem which was stated to be NP-complete by Schaefer in his famous dichotomy theorem paper although he did not give the proof for cubic planar graphs. The problem asks for the existence of two coloring of cubic planar graphs such that every vertex has exactly one neighbor of the same color as itself.

EDIT: Defective coloring is the decision version of your problem. A graph is (k, d)-colorable if one can color the vertices with k colors such that no vertex is adjacent to more than d vertices of its same color. The decision problem (2,1)-coloring with defects, which is equivalent to your optimization problem, was shown to be NP-complete even for planar graphs.

share|cite|improve this answer
What is a reduction from "2-colorable perfect matching in cubic planar graphs" to Yixin's problem? – Ricky Demer Nov 9 '12 at 22:14
2-colorable perfect matching is a special case where the maximum connected component size exactly equals C. – Mohammad Al-Turkistany Nov 9 '12 at 22:20
Thanks for your answer, but I cannot concur with you. As in the "2-colorable perfect matching in cubic planar graphs" problem, EACH component needs to be exactly 2. But my question seems easier. – Yixin Cao Nov 9 '12 at 22:32
Yes, I missed that difference. – Mohammad Al-Turkistany Nov 9 '12 at 22:40

Your Answer


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.