# 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 :
Document type :
Conference papers
Domain :

Cited literature [16 references]

https://hal.inria.fr/hal-01184374
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, August 14, 2015 - 11:38:14 AM
Last modification on : Wednesday, November 10, 2021 - 5:38:03 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:03:21 AM

### File

dmAE0109.pdf
Publisher files allowed on an open archive

### Citation

Peter Bella, Daniel Král, Bojan Mohar, Katarina Quittnerová. Labeling planar graphs with a condition at distance two. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.41-44, ⟨10.46298/dmtcs.3417⟩. ⟨hal-01184374⟩

Record views