Optimal channel assignment and L(p, 1)-labeling

The optimal channel assignment is an important optimization problem with applications in optical networks. This problem was formulated to the L(p, 1)-labeling of graphs by Griggs and Yeh (SIAM J Discrete Math 5:586–595, 1992). A k-L(p, 1)-labeling of a graph G is a function f: V(G) → { 0 , 1 , 2 , … , k} such that | f(u) - f(v) | ≥ p if d(u, v) = 1 and | f(u) - f(v) | ≥ 1 if d(u, v) = 2 , where d(u, v) is the distance between the two vertices u and v in the graph. Denote λp,1l(G)=min{k∣G has a list k-L(p, 1)-labeling}. In this paper we show upper bounds λ1,1l(G)≤Δ+9 and λ2,1l(G)≤max{Δ+15,29} for planar graphs G without 4- and 6-cycles, where Δ is the maximum vertex degree of G. Our proofs are constructive, which can be turned to a labeling (channel assignment) method to reach the upper bounds.