Full L(2,1) - colorings of Graphs and the Channel Assignment
Problem

Speaker      :      Mr. Fred S.Roberts, Director, DIMACS, Rutgers University

Time             :      Friday, February, 16th, 3:00 pm - 4:00 pm.

Location      :     E1 Building, Room # 242 (E1 242) 

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