An improper planar coloring with monochromatic component size $\leq 2$

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

-

1 Answer

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.

-
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