Divisibility and \(T\)-span of graphs (Q5936063)

Assume that \(G\) is a simple graph and \(T\) is a \(T\)-set, i.e. a finite set of nonnegative integers such that \(0\) is in \(T\). A \(T\)-coloring of \(G\) is any function \(c\) that assigns an integer (color) \(c(v)\) to each vertex \(v\) of \(G\) in such a way that if two vertices \(u\), \(v\) are adjacent then \(|c(u)- c(v)|\not\in T\). The \(T\)-span of \(G\), denoted \(\text{sp}_T(G)\), is the minimal span over all possible \(T\)-colorings of \(G\), where the span of a \(T\)-coloring \(c\) of \(G\) is the distance between the smallest and the largest color used by \(c\). This paper studies the properties of the \(T\)-span with respect to divisibility. In particular, the author shows that if a positive integer \(d\) divides all elements of the set \(\{0,1,\dots,\max T+1\}\setminus T\) then \(\text{sp}_T(G)\) is divisible by \(d\) and the quotient \(\text{sp}_T(G)/d\) equals \(\text{sp}_S(G)\), where \(S= \{t\mid dt\in T\}\). He also shows that for any positive integer \(d\), if \(S= \{0,1,\dots, d(\max T+1)\}\setminus\{dt\mid t\not\in T\}\) then \(\text{sp}_S(G)= d\text{ sp}_T(G)\). As a result of these considerations we obtain simple formulas describing the \(T\)-span for many new \(T\)-sets.