Fred S. Roberts
(Department of Mathematics, Rutgers University, and Director DIMACS)
Full L(2,1)-colorings of Graphs and the Channel Assignment Problem
Abstract
L(2,1)-colorings of graphs assign integers to vertices so that
colors assigned to adjacent vertices differ by at least 2 and colors assigned
to vertices at distance 2 in the graph differ by at least 1. L(2,1)-colorings
first arose as a generalization of
T-colorings that were motivated by problems of assigning frequencies
to channels in communications problems and were first investigated extensively
by Jerry Griggs and Roger Yeh. The span of a graph G
is the smallest k so that there is an L(2,1)-coloring using
integers between 0 and k. Motivated by heuristic algorithms arising
in channel assignment, we discuss the problem of identifying graphs
which have a full L(2,1)-coloring, i.e., an L(2,1)-coloring
of optimal span in which every color between the smallest and largest is
actually used on some vertex. This is joint work with Peter Fishburn. |
|