The List L(2, 1)-Labeling of Planar Graphs with Large Girth

A list assignment of a graph G is a function \(L: V(G)\longrightarrow 2^{N}\) that assigns each vertex v a list L(v) for all \(v\in V(G)\). We say that G has an L-L(2, 1)-labeling if there exists a function \(\phi \) such that \(\phi (v)\in L(v)\) for all \(v\in V(G)\), \(|\phi (u)-\phi (v)|\ge 2\) if \(d(u, v)=1\) and \(|\phi (u)-\phi (v)|\ge 1\) if \(d(u, v)=2\). The list L(2, 1)-labeling number of G, denoted by \(\lambda _{2,1}^{l}(G)\), is the minimum k such that for every list assignment \(L=\{L(v){:}\,|L(v)|=k,\ v\in V(G)\}\), G has an L-L(2, 1)-labeling. We prove that for planar graph G with maximum degree \(\varDelta (G)\) and girth g(G), \(\lambda _{2,1}^{l}(G)\le \varDelta (G)+3\) holds if \(\varDelta (G)=4\) and \(g(G)\ge 19\) or \(\varDelta (G)=3\) and \(g(G)\ge 32\). Moreover, there exist planar graphs having \(\lambda _{2,1}^{l}(G)=\varDelta (G)+3\) for arbitrarily large \(\varDelta (G)\).