\(T\)-colorings of graphs (Q1197028)

Given a finite set \(T\) of natural numbers containing 0, a \(T\)-coloring of a simple graph \(G=(V(G),E(G))\) is a function \(f\) from the vertex set \(V(G)\) to natural numbers such that \(| f(u)-f(v)|\notin T\) whenever \(\{u,v\}\in E(G)\). The span of a \(T\)-coloring is defined to be the difference between the largest and smallest color used. The \(T\)-span of \(G\), denoted by \(\text{sp}_ T(G)\), is the minimum span among all \(T\)-colorings of \(G\). A graph \(G\) is weakly perfect if the chromatic number \(\chi(G)\) is equal to the clique number \(\omega(G)\). A special graph \(G^ n_ T\) plays an important role in this paper. The vertex set of \(G^ n_ T\) is \(\{0,1,2,\ldots,n-1\}\) and \(\{u,v\}\in E(G^ n_ T)\) if and only if \(| u-v|\notin T\). The main theorem shows that, given \(T\), the following are equivalent: (i) \(\text{sp}_ T(G)=\text{sp}_ T(K_{\chi(G)})\) for all graphs \(G\), (ii) \(\text{sp}_ T(G^ n_ T)=\text{sp}_ T(K_{\chi(G^ n_ T)})\) for all \(n\), (iii) \(G^ n_ T\) is weakly perfect for all \(n\). Using these equivalences, known results about sets \(T\) which satisfy (i) are derived with shorter proofs. New families of sets \(T\) with this property are also constructed. Finally, it is established that \(\text{sp}_ T(G)=\text{sp}_ T(K_ m)=n-1\) for all graphs \(G\) with \(\chi(G)=m\) if and only if \(\omega(G^ n_ T)=\chi(G^ n_ T)=m\) and \(\chi(G_ T^{n-1})<\chi(G^ n_ T)\).