Colourful theorems and indices of homomorphism complexes
type: Item
instance of: scholarly article
title: Colourful theorems and indices of homomorphism complexes
zbMATH Open document ID: 1266.05041
author: Claude Tardif
author: Ambrus Zsbán
author: Gábor Simonyi
published in: The Electronic Journal of Combinatorics
publication date: 2013-06-07T00:00:00Z
full work available at URL: v20i1p10
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 6171849
zbMATH Keywords: graph theory topological bounds
zbMATH Keywords: chromatic numbers
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 6171849