An extremal problem on non-full colorable graphs (Q2384400)

For a given graph \(G\) of order \(n(G)\), a \(k\)-\(L(2,1)\)-labeling is defined as \(f: V(G)\to \{ 1,2,\dots,k\}\) such that \(| f(u)-f(v)| \geq 2\) when \(\text{dist}_G(u,v)=1\) and \(| f(u)-f(v)| \geq 1\) when \(\text{dist}_G(u,v)=2\). The \(L(2,1)\)-labeling number of \(G\), \(\lambda (G)\), is the smallest number \(k\) such that \(G\) has a \(k\)-\(L(2,1)\)-labeling. The hole index \(\rho (G)\) of \(G\) is the minimum number of integers not used in a \(\lambda (G)\)-\(L(2,1)\)-labeling of \(G\). Graphs with \(\lambda (G)=2m\) and \(\rho (G)=m\) for a positive integer \(m\) are considered in the paper. A graph \(G\) belongs to the family \(G(k,m)\) if and only if \(G\) is \((m+1)\)-partite with \(V(G)=V_0\cup V_1\cup\dots\cup V_m\) where \(| V_0| =| V_1| =\dots =| V_m| =k\) and for every \(0\leq i<j\leq m\) the subgraph induced on \(V_i\cup V_j\) is a perfect matching. It is proved for every integer \(m\geq 1\) that if \(\lambda (G)=2m\) and \(\rho (G)=m\), then \(G\in G(k,m)\) for some integer \(k\geq 1\). Further it is proved that \(n(G) =2m+1,\lambda (G)=2m\), and \(\rho (G)=m\) if and only if \(G\in G(2,m)\). It is also shown that for any \(k\geq 3\) and \(m\geq 2\) there exists a connected graph \(G\in G(k,m)\) with \(\lambda (G)=2m\) and \(\rho (G)=0\).