Back to Search
Start Over
Labeling Planar Graphs with Conditions on Girth and Distance Two
- Source :
- SIAM Journal on Discrete Mathematics. 17:264-275
- Publication Year :
- 2003
- Publisher :
- Society for Industrial & Applied Mathematics (SIAM), 2003.
-
Abstract
- For a planar graph $G$, let $\Delta(G)$, $g(G)$, and $\lambda(G;p,q)$ denote, respectively, its maximum degree, girth, and $L(p,q)$-labeling number. We prove that (1) $\lambda(G;p,q)\le (2q-1)\Delta(G)+4p+4q-4$ if $g(G)\ge 7$; (2) $\lambda(G;p,q)\le (2q-1)\Delta(G)+6p+12q-9$ if $g(G)\ge 6$; (3) $\lambda(G;p,q)\le (2q-1)\Delta(G)+6p+24q-15$ if $g(G)\ge 5$. These bounds have consequences on conjectures by Wegner [Graphs with Given Diameter and a Coloring Problem, preprint, University of Dortmund, Dortmund, Germany, 1977] and Griggs and Yeh [SIAM J. Discrete Math., 5 (1992), pp. 586--595].
Details
- ISSN :
- 10957146 and 08954801
- Volume :
- 17
- Database :
- OpenAIRE
- Journal :
- SIAM Journal on Discrete Mathematics
- Accession number :
- edsair.doi...........6b8a9b31698a4ed82a0286148eb44c68