The number of defective colorings of graphs on surfaces
A (k, 1)-coloring of a graph is a vertex-coloring with k colors such that each vertex is permitted at most 1 neighbor of the same color. We show that every planar graph has at least c?n distinct (4, 1)-colorings, where c is constant and ??1.466 satisfies ?3 = ?2 + 1. On the other hand for any ?>0, we give examples of planar graphs with fewer than c(? + ?)n distinct (4, 1)-colorings, where c is constant and . Let ?(S) denote the chromatic number of a surface S. For every surface S except the sphere, we show that there exists a constant c? = c?(S)>0 such that every graph embeddable in S has at least c?2n distinct (?(S), 1)-colorings.  2010 Wiley Periodicals, Inc. J Graph Theory 28:129-136, 2011
planar graphs graph coloring