Colourful theorems and indices of homomorphism complexes (Q1953386): Difference between revisions

Summary: We extend the colourful complete bipartite subgraph theorems of [\textit{G. Simonyi} and \textit{G. Tardos}, Combinatorica 26, No. 5, 587--626 (2006; Zbl 1121.05050); Eur. J. Comb. 28, No. 8, 2188--2200 (2007; Zbl 1125.05042)] 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.