Griggs and Yeh's Conjecture and L(p,1)-labelings

Frédéric Havet 1 Bruce Reed Jean-Sébastien Sereni 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : An L(p,1)-labeling of a graph is a function f from the vertex set to the positive integers such that |f(x) − f(y)| ≥ p if dist(x, y) = 1 and |f(x) − f(y)| ≥ 1 if dist(x, y) = 2, where dist(x,y) is the distance between the two vertices x and y in the graph. The span of an L(p,1)- labeling f is the difference between the largest and the smallest labels used by f. In 1992, Griggs and Yeh conjectured that every graph with maximum degree Δ ≥ 2 has an L(2, 1)-labeling with span at most Δ^2. We settle this conjecture for Δ sufficiently large. More generally, we show that for any positive integer p there exists a constant Δ_p such that every graph with maximum degree Δ ≥ Δ_p has an L(p,1)-labeling with span at most Δ^2. This yields that for each positive integer p, there is an integer C_p such that every graph with maximum degree Δ has an L(p,1)-labeling with span at most Δ^2 + C_p.
Document type :
Journal articles
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/inria-00327909
Contributor : Jean-Sébastien Sereni <>
Submitted on : Monday, March 5, 2012 - 8:48:34 AM
Last modification on : Friday, April 19, 2019 - 11:12:03 AM
Long-term archiving on : Wednesday, December 14, 2016 - 10:38:55 AM

File

HRS12.pdf
Publisher files allowed on an open archive

Identifiers

Citation

Frédéric Havet, Bruce Reed, Jean-Sébastien Sereni. Griggs and Yeh's Conjecture and L(p,1)-labelings. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2012, 26 (1), pp.145--168. ⟨10.1137/090763998⟩. ⟨inria-00327909v2⟩

Share

Metrics

Record views

475

Files downloads

509