Skip to Main content Skip to Navigation
Conference papers

L(2,1)-labelling of graphs

Frédéric Havet 1 Bruce Reed 1 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(2,1)$-labelling of a graph is a function $f$ from the vertex set to the positive integers such that $|f(x)-f(y)|\geq 2$ if $dist(x,y)=1$ and $|f(x)-f(y)|\geq 1$ if $dist(x,y)=2$, where $dist(u,v)$ is the distance between the two vertices~$u$ and~$v$ in the graph $G$. The \emph{span} of an $L(2,1)$-labelling $f$ is the difference between the largest and the smallest labels used by $f$ plus $1$. In 1992, Griggs and Yeh conjectured that every graph with maximum degree $\Delta\geq 2$ has an $L(2,1)$-labelling with span at most $\Delta^2+1$. We settle this conjecture for $\Delta$ sufficiently large.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : David Coudert <>
Submitted on : Tuesday, May 25, 2010 - 11:45:38 AM
Last modification on : Monday, October 12, 2020 - 10:30:21 AM
Long-term archiving on: : Thursday, December 1, 2016 - 12:42:20 AM


Files produced by the author(s)


  • HAL Id : inria-00486183, version 1


Frédéric Havet, Bruce Reed, Jean-Sébastien Sereni. L(2,1)-labelling of graphs. ACM-SIAM symposium on Discrete algorithms (SODA 2008), Jan 2008, San Francisco, California, United States. pp.621-630. ⟨inria-00486183⟩



Record views


Files downloads