Brooks type result for distance constrained labeling of graphs
摘要
Distance constrained labelings of graphs naturally form
an important model for radio frequency assignment problems. An
L(p1,...,pk)-labeling of a graph G for integers p1,...,pk
is a labeling of its vertices by non-negative integers such that
the labels of two vertices at distance i differ by at least pi .
The least number K for which there is proper
L(p1,...,pk)-labeling by integers between 0 and K is denoted
lp1,...,pk(G). Note that
l1,...,1(G)+1 is
the chromatic number of the k-th power of G.
We present several results on L(p1,...,pk)-labelings of
graphs. Griggs and Yeh conjectured in 1992 that
l2,1(G)
£
D2 for every graph G of maximum degree D. We provide an
analogue of Brooks Theorem for channel assignment problem and
derive as its consequence that
l2,1(G)
£
D2+D-1 for
every such graph G. This is the best known general upper on
l2,1(G) in terms of maximal degree D. The conjecture of
Griggs and Yeh have been verified for several special classes of
graphs, including chordal graphs.
∼Daniel Kral 教授演講摘要∼