Abstract
For an integer k }= 1, the kth interleaved adjoint of a digraph G is the digraph l(k)(G) with vertex-set V(G)(k), and arcs ((u(1), ... ,u(k)). (v(1), ... , v(k))) such that (u(i), v(i)) is an element of A(G) for i = 1, ... , k and (v(i), u(i+1)) is an element of A(G) for i = 1, ... , k - 1. For every k, we derive upper and lower bounds for the chromatic number of l(k)(G) in terms of that of G.
In the case where G is a transitive tournament, the exact value of the chromatic number of l(k)(G) has been determined by [H.G. Yeh, X.
Zhu, Resource-sharing system scheduling and circular chromatic number, Theoret. Comput.
Sci. 332 (2005) 447-460]. We use the latter result in conjunction with categorical properties of adjoint functors to derive the following consequence.
For every integer l, there exists a directed path Q(l) of algebraic length l which admits homomorphisms into every directed graph of chromatic number at least 4. We discuss a possible impact of this approach on the multifactor version of the weak Hedetniemi conjecture.