# Labeling planar graphs with a condition at distance two

Abstract : An $L(2,1)$-labeling of a graph is a mapping $c:V(G) \to \{0,\ldots,K\}$ such that the labels assigned to neighboring vertices differ by at least $2$ and the labels of vertices at distance two are different. Griggs and Yeh [SIAM J. Discrete Math. 5 (1992), 586―595] conjectured that every graph $G$ with maximum degree $\Delta$ has an $L(2,1)$-labeling with $K \leq \Delta^2$. We verify the conjecture for planar graphs with maximum degree $\Delta \neq 3$.
Keywords :
Type de document :
Communication dans un congrès
Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.41-44, 2005, DMTCS Proceedings
Domaine :

Littérature citée [16 références]

https://hal.inria.fr/hal-01184374
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 14 août 2015 - 11:38:14
Dernière modification le : jeudi 11 mai 2017 - 01:02:53
Document(s) archivé(s) le : dimanche 15 novembre 2015 - 11:03:21

### Fichier

dmAE0109.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01184374, version 1

### Citation

Peter Bella, Daniel Král, Bojan Mohar, Katarina Quittnerová. Labeling planar graphs with a condition at distance two. Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.41-44, 2005, DMTCS Proceedings. 〈hal-01184374〉

### Métriques

Consultations de la notice

## 303

Téléchargements de fichiers