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

From MaRDI portal
Added link to MaRDI item.
Import240304020342 (talk | contribs)
Set profile property.
 
(2 intermediate revisions by one other user not shown)
Property / author
 
Property / author: Gábor Simonyi / rank
Normal rank
 
Property / author
 
Property / author: Gábor Simonyi / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank

Latest revision as of 05:21, 5 March 2024

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
    graph theory topological bounds
    0 references
    chromatic numbers
    0 references

    Identifiers