An extremal problem on non-full colorable graphs

For a given graph G of order n, a k  -L(2,1)L(2,1)-labelling is defined as a function f:V(G)→{0,1,2,…k}f:V(G)→{0,1,2,…k} such that |f(u)-f(v)|⩾2|f(u)-f(v)|⩾2 when dG(u,v)=1dG(u,v)=1 and |f(u)-f(v)|⩾1|f(u)-f(v)|⩾1 when dG(u,v)=2dG(u,v)=2. The L(2,1)L(2,1)-labelling number of G  , denoted by λ(G)λ(G), is the smallest number k such that G has a k  -L(2,1)L(2,1)-labelling. The hole index ρ(G)ρ(G) of G   is the minimum number of integers not used in a λ(G)λ(G)-L(2,1)L(2,1)-labelling of G. We say G   is full-colorable if ρ(G)=0ρ(G)=0; otherwise, it will be called non-full colorable. In this paper, we consider the graphs with λ(G)=2mλ(G)=2m and ρ(G)=mρ(G)=m, where m   is a positive integer. Our main work generalized a result by Fishburn and Roberts [No-hole L(2,1)L(2,1)-colorings, Discrete Appl. Math. 130 (2003) 513–519].