<p>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.</p>

<p>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 <a href="http://dspace.mit.edu/bitstream/handle/1721.1/37006/33976498.pdf?sequence=1" rel="nofollow">NP-complete even for planar</a> graphs.</p>

CC BY-SA 3.0
2012-11-09T22:20:15.100Z
2-colorable perfect matching is a special case where the maximum connected component size exactly equals C.
Mohammad Al-Turkistany
CC BY-SA 3.0
2012-11-09T22:32:07.153Z
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
CC BY-SA 3.0
2012-11-09T22:40:56.447Z
Yes, I missed that difference.
Mohammad Al-Turkistany
CC BY-SA 3.0
2012-11-09T21:36:40.277Z
2012-11-10T15:15:47.087Z
2012-11-10T15:15:47.087Z
Mohammad Al-Turkistany
<p>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 <strong>the minimum number $\lambda$ of colors needed to color a graph such that largest monochromatic component has size no more than $C$.</strong><br>
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.   </p>

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

<p>This can be viewed as a dual problem of what is studied by <a href="http://dx.doi.org/10.1016/j.dam.2004.10.005">Edwards and Farr</a>, where $\lambda$ is fixed, and one is asked to find the minimum size of $C$.</p>

<cc.complexity-theory><graph-theory><graph-colouring><planar-graphs>
An improper planar coloring with monochromatic component size $\leq 2$
Yixin Cao
# An improper planar coloring with monochromatic component size $\leq 2$

(Asked by: username_0 on 2012-11-08)

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](http://dx.doi.org/10.1016/j.dam.2004.10.005), where $\lambda$ is fixed, and one is asked to find the minimum size of $C$.

**Tags:** cc.complexity-theory, graph-theory, graph-colouring, planar-graphs

---

## 1 answers

### Answer by username_1 on 2012-11-09. Score: 3 | Accepted 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](http://dspace.mit.edu/bitstream/handle/1721.1/37006/33976498.pdf?sequence=1) graphs.

> **Comments:**
> **username_1**: 2-colorable perfect matching is a special case where the maximum connected component size exactly equals C.  
> **username_0**: 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.  
> **username_1**: Yes, I missed that difference.  

---

