**NB:** A
PDF
version of this announcement (suitable for posting)
is also available.
# Full L(2,1)-colorings of Graphs
and the Channel Assignment Problem

### Fred S. Roberts

Rutgers University

###
Monday, September 24, 2001

102 Bradley Hall, 4 pm

Tea 3:30 pm, Math Lounge

**Abstract:
** We shall study a generalization of the notion of
graph coloring that arose from practical problems of assigning
frequencies to channels in communications problems. 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 from frequency assignment problems studied in connection
with 10,000-vertex European networks 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 C. Fishburn (AT&T
Labs).

This talk will be accessible to graduate students.