Manchester Metropolitan University's Research Repository

Interleaved adjoints of directed graphs

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


Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (142kB) | Preview


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.

Impact and Reach


Activity Overview

Additional statistics for this dataset are available via IRStats2.


Actions (login required)

Edit Item Edit Item