The line digraph construction has been utilised in [1]}, [2]} as a polynomial-time (and in fact log-space) reduction between \(\operatorname{PCSP}\) s. In particular, the construction changes the chromatic number in a controlled way, as we now describe.
Consider the integer functions \(a\)  and \(b\)  defined by \(a(p)=2^p\)  and \(b(p)={p\atopwithdelims (){p/2}}\)  for \(p\in \mathbb {N}\) , and notice that \(a(p)\ge b(p)\)  for each \(p\) . Let also \(a^{(i)}\)  (resp. \(b^{(i)}\) ) be the function obtained by iterating \(a\)  (resp. \(b\) ) \(i\) -many times, for \(i\in \mathbb {N}\) . The following result bounds the chromatic number of the line digraph in terms of that of the original digraph.
