Optimal frequency assignment and planar list L(2, 1)-labeling

2021 
G has a list k-L(2, 1)-labeling if for any k-list assignment L, there exists a coloring $$c:V(G)\rightarrow \bigcup \limits _{v\in V} L(v)$$ of G such that $$c(v)\in L(v)$$ for $$\forall v\in V(G)$$ and for $$\forall u,v\in V(G)$$ , $$|c(u)-c(v)|\ge 2$$ if $$d(u,v)=1$$ , $$|c(u)-c(v)|\ge 1$$ if $$d(u,v)=2$$ . $$\lambda _{2,1}^{l}(G)=\min \{k|G$$ has a list k-L(2, 1)-labeling $$\}$$ is called the list L(2, 1)-labeling number of G. In this paper, we prove that for planar graph with maximum degree $$\Delta \ge 5$$ , girth $$g\ge 13$$ and without adjacent 13-cycles, $$\lambda _{2,1}^{l}(G)\le \Delta +3$$ holds. Moreover, the upper bound $$\Delta +3$$ is tight.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    21
    References
    0
    Citations
    NaN
    KQI
    []