DIMACS TR: 2000-32
Minimal Forbidden Graphs for L(2,1)-Colorings
Authors: Peter C. Fishburn and Fred S. Roberts
ABSTRACT
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