Interleaved adjoints of directed graphs

Foniok, J, Nesetril, J and Tardif, C (2011) Interleaved adjoints of directed graphs. EUROPEAN JOURNAL OF COMBINATORICS, 32. ISSN 0195-6698

Preview

Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (142kB) | Preview

Abstract

For an integer k≥1k≥1, the kkth interleaved adjoint of a digraph GG is the digraph ιk(G)ιk(G) with vertex-set V(G)kV(G)k, and arcs ((u1,…,uk),(v1,…,vk))((u1,…,uk),(v1,…,vk)) such that (ui,vi)∈A(G)(ui,vi)∈A(G) for i=1,…,ki=1,…,k and (vi,ui+1)∈A(G)(vi,ui+1)∈A(G) for i=1,…,k−1i=1,…,k−1. For every kk, we derive upper and lower bounds for the chromatic number of ιk(G)ιk(G) in terms of that of GG. In the case where GG is a transitive tournament, the exact value of the chromatic number of ιk(G)ι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 ℓℓ, there exists a directed path QℓQℓ of algebraic length ℓℓ which admits homomorphisms into every directed graph of chromatic number at least 44. We discuss a possible impact of this approach on the multifactor version of the weak Hedetniemi conjecture.