## 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