<i>L(2,1)</i> -labeling of planar graphs

Abstract

In this paper we prove a conjecture left open by Bodlaender et al. [3] concerning L(2, 1)-labeling of outerplanar graphs. L(2, 1)-labeling is a coloring problem arising from frequency assignment in multihop radio networks, in which adjacent nodes must receive colors that are at least two apart while nodes at distance two must receive different colors. Namely, we improve the best known upper bound from Δ + 9 to Δ + 3 colors, Δ being the maximum degree of the graph and Δ ⪈ 8. Consequently, we improve the additive term for triangulated outerplanar graphs from Δ + 7 to Δ + 2, and for planar graphs from 3Δ + 29 to 3Δ + 8. We also make a step towards the improvement of the factor 3 in the bound of planar graphs; in fact we prove that for hamiltonian planar graphs 2Δ + 6 colors are sufficient.