L(2,1)-labelling of graphs

Résumé : 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.
Type de document :
Communication dans un congrès
ACM-SIAM symposium on Discrete algorithms (SODA 2008), Jan 2008, San Francisco, California, United States. pp.621-630, 2008, <http://portal.acm.org/citation.cfm?id=1347082.1347151>
Liste complète des métadonnées

https://hal.inria.fr/inria-00486183
Contributeur : David Coudert <>
Soumis le : mardi 25 mai 2010 - 11:45:38
Dernière modification le : mercredi 12 octobre 2016 - 01:23:13
Document(s) archivé(s) le : jeudi 1 décembre 2016 - 00:42:20

Fichier

HRS08.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00486183, version 1

Collections

Citation

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, 2008, <http://portal.acm.org/citation.cfm?id=1347082.1347151>. <inria-00486183>

Partager

Métriques

Consultations de
la notice

210

Téléchargements du document

124