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.