Colourful theorems and indices of homomorphism complexes (Q1953386)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Colourful theorems and indices of homomorphism complexes
scientific article

    Statements

    Colourful theorems and indices of homomorphism complexes (English)
    0 references
    0 references
    0 references
    0 references
    7 June 2013
    0 references
    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.
    0 references
    0 references
    graph theory topological bounds
    0 references
    chromatic numbers
    0 references