LAUSR

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)\rightarrow \{0,1,2,\ldots ,k\}$$f:V(G)→{0,1,2,…,k} such that $$|f(u)-f(v)|\ge p$$|f(u)-f(v)|≥p if $$d(u,v)=1$$d(u,v)=1 and $$|f(u)-f(v)|\ge 1$$|f(u)-f(v)|≥1 if $$d(u,v)=2$$d(u,v)=2, where d(u, v) is the distance between the two vertices u and v in the graph. Denote $$\lambda _{p,1}^l(G)= \min \{k \mid G$$λp,1l(G)=min{k∣G has a list k-L(p, 1)-labeling$$\}$$}. In this paper we show upper bounds $$\lambda _{1,1}^l(G)\le \Delta +9$$λ1,1l(G)≤Δ+9 and $$\lambda _{2,1}^l(G)\le \max \{\Delta +15,29\}$$λ2,1l(G)≤max{Δ+15,29} for planar graphs G without 4- and 6-cycles, where $$\Delta $$Δ 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.