e-space
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

[img]
Preview

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.

Impact and Reach

Statistics

Downloads
Activity Overview
25Downloads
66Hits

Additional statistics for this dataset are available via IRStats2.

Altmetric

Actions (login required)

Edit Item Edit Item