Labeling Planar Graphs with Conditions on Girth and Distance Two

Source 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].