DIMACS TR: 2000-32

Minimal Forbidden Graphs for L(2,1)-Colorings

Authors: Peter C. Fishburn and Fred S. Roberts


The span $\lambda(G)$ of a graph G is the smallest k for which G's vertices can be L(2,1)-colored, i.e., colored with integers in {0,1,...,k} so that adjacent vertices' colors differ by as least two, and colors of vertices at distance two differ. We study minimal forbidden graphs, graphs with the property that every proper subgraph has smaller span. Fixing the maximum degree, we observe that the first nontrivial case involves minimal forbidden graphs of maximum degree 3 and span 5. We present examples to illustrate the variety of graphs with this property and in particular provide several infinite families of such graphs.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-32.ps.gz
DIMACS Home Page