DIMACS TR: 95-26
Defective Coloring of Toroidal Graphs and Graphs of Bounded Benus
Authors: Lenore Cowen and Wayne Goddard
A graph is (k,d)-colorable if one can color the vertices with k colors such
that no vertex is adjacent to more than d vertices of the same color. In
this paper we investigate the existence of such colorings in surfaces.
It is shown that a toroidal graph is (3,2)- and (5,1)-colorable, and
that a graph of genus g is (X(g) /(d+1) + 4,d)-colorable, where X(g) is the
maximum chromatic number of a graph embeddable on the surface of genus g.
Paper available at:
DIMACS Home Page