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