Given a planar graph how can I color its vertices with 2 colors, A and B, given that:
- Color A cannot have a neighbor of color A and should have 1 or more neighbors of color B
- Color B can have any number of neighbors of color B and should have 1 or more neighbors of color A
Anybody knows the name of an algorithm for such coloring or the name of a coloring like this or a way to solve it?
Given such a coloring, the vertices of color A form an independent dominating set, and conversely, given an independent dominating set, you can color its vertices with color A and the rest of the vertices with color B to get a suitable coloring. This is assuming that the graph contains no isolated vertices, but this is clearly necessary for the existence of such a coloring.
If you just want to find any such coloring, you can greedily take a maximal independent set; this will give you an independent dominating set. Finding the smallest independent dominating set appears to be NP-hard, even for planar graphs. As for concrete bounds, Theorem 5.1. in this survey gives an algorithm that, given a $k$-coloring (in the usual sense!) of the graph, finds an indepent dominating set of size $(k−1)n/k−(k−2)$. Practically, this gives you an independent dominating set of size $4n/5 - 3$, since there are fast algorithms for finding a five-coloring of a planar graph (while finding a four-coloring is difficult at this point).