Premium
The number of defective colorings of graphs on surfaces
Author(s) -
Rackham Tom
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20546
Subject(s) - combinatorics , mathematics , planar graph , vertex (graph theory) , graph , list coloring , chromatic scale , constant (computer programming) , complete coloring , fractional coloring , edge coloring , graph coloring , discrete mathematics , graph power , line graph , computer science , programming language
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 ′2 n distinct (γ( S ), 1)‐colorings. © 2010 Wiley Periodicals, Inc. J Graph Theory 28:129‐136, 2011