Peter Bella ; Daniel Král ; Bojan Mohar ; Katarina Quittnerová - Labeling planar graphs with a condition at distance two

dmtcs:3417 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3417
Labeling planar graphs with a condition at distance twoArticle

Authors: Peter Bella ORCID1; Daniel Král ORCID2; Bojan Mohar 3; Katarina Quittnerová 4

  • 1 Department of Mathematical Analysis
  • 2 Department of Applied Mathematics [Prague]
  • 3 Department of Mathematics
  • 4 Faculty of Mathematics and Physics [Ljubljana]

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$.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: $L(2 1)$-labeling,channel assignment problem,graph coloring,planar graphs,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

1 Document citing this article

Consultation statistics

This page has been seen 211 times.
This article's PDF has been downloaded 353 times.