Skip to Main content Skip to Navigation
Conference papers

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$.
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184374
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 11:38:14 AM
Last modification on : Friday, March 15, 2019 - 4:55:06 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:03:21 AM

File

dmAE0109.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184374, version 1

Collections

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. ⟨hal-01184374⟩

Share

Metrics

Record views

358

Files downloads

949