Abstract:

Let p and q be two positive integers with p≥q, and let λ_p,q(G) be the L(p,q)-labeling number of a planar graph G. It is proved that λ_p,q(G)≤(2q-1)Δ(G)+6p+10q-8 if  G is a planar graphs with girth g(G)≥5, which implies Wegner’s conjecture holds for a planar graph G with girth g(G)≥5 and Δ(G)≥16.

Key words:  planar graph;girth; L(p,q)-labeling; L(p,q)-labeling number