Defective choosability of graphs in surfaces
Douglas R. Woodall · Discussiones Mathematicae Graph Theory · 2011
It is known that if G is a graph that can be drawn without edges crossing in a surface with Euler characteristic �, and k and d are positive integers such that k > 3 and d is sufficiently large in terms of k and �, then G is (k;d) � -colorable; that is, the vertices of G can be colored with k colors so that each vertex has at most d neighbors with the same color as itself. In this paper, the known lower bound on d that suffices for this is reduced, and an analogous result is proved f or