The number of defective colorings of graphs on surfaces |
| |
Authors: | Tom Rackham |
| |
Affiliation: | Mathematical Institute, University of Oxford OX1 3LB, United Kingdom |
| |
Abstract: | 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 |
| |
Keywords: | graph coloring planar graphs |
|
|