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. |
Year | Venue | Keywords |
---|---|---|
2013 | ELECTRONIC JOURNAL OF COMBINATORICS | Topological bounds,Chromatic numbers |
Field | DocType | Volume |
Discrete mathematics,Graph,Clique number,Combinatorics,Chromatic scale,Bipartite graph,Duality (optimization),Homomorphism,Mathematics | Journal | 20.0 |
Issue | ISSN | Citations |
1.0 | 1077-8926 | 5 |
PageRank | References | Authors |
0.54 | 12 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Gábor Simonyi | 1 | 249 | 29.78 |
Claude Tardif | 2 | 341 | 38.08 |
Ambrus Zsbán | 3 | 12 | 1.98 |