L(2,1)-labelling of graphs

Description

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.

Abstract (French)

Un $L(2,1)$-étiquettage d'un graphe est une fonction $f$ de l'ensemble des sommets vers les entiers positifs telle que $|f(x)-f(y)|\geq 2$ si $dist(x,y)=1$ et $|f(x)-f(y)|\geq 1$ si $dist(x,y)=2$, où $dist(u,v)$ est la distance entre les sommets~$u$ et~$v$ dans le graphe $G$. Le \emph{span} d'un $L(2,1)$-étiquettage $f$ est la différence entre la plus grande et la plus petite étiquette utilisée par $f$ plus $1$. En 1992, Griggs et Yeh ont conjecturé que tout graphe de degré maximum $\Delta\geq 2$ a un $L(2,1)$-étiquettage de span au plus $\Delta^2+1$. Nous confirmons cette conjecture pour $\Delta$ suffisamment grand.

Abstract

International audience

Additional details