Colourful Theorems and Indices of Homomorphism Complexes

Abstract

We extend the colourful complete bipartite subgraph theorems of [G. Simonyi, G. Tardos, Local chromatic number, Ky Fan's theorem,  and circular colorings, Combinatorica 26 (2006), 587--626] and [G. Simonyi, G. Tardos, Colorful subgraphs of Kneser-like graphs, European J. Combin. 28 (2007), 2188--2200] to more general topological settings. We give examples showing that the hypotheses are indeed more general. We use our results to show that the topological bounds on chromatic numbers of digraphs with tree duality are at most one better than the clique number. We investigate combinatorial and complexity-theoretic aspects of relevant order-theoretic maps.