95-26 Defective Coloring of Toroidal Graphs and Graphs of Bounded Benus

DIMACS TR: 95-26

Defective Coloring of Toroidal Graphs and Graphs of Bounded Benus

Authors: Lenore Cowen and Wayne Goddard

ABSTRACT
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: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-26.ps.gz

DIMACS Home Page