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.
 
Last updated by  am@charlie.iit.edu  on 01/27/01