Geodesic
Colourful theorems and indices of homomorphism complexes
Gábor Simonyi1 ; Claude Tardif2 ; Ambrus Zsbán3
1Hungarian Academy of Sciences
2Royal Military College of Canada
3Budapest University of Technology and Economics
The electronic journal of combinatorics, Tome 20 (2013) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/2302
Classification : 05C15, 05C55
Mots-clés : graph theory topological bounds, chromatic numbers

Gábor Simonyi  1   ; Claude Tardif  2   ; Ambrus Zsbán  3

1 Hungarian Academy of Sciences
2 Royal Military College of Canada
3 Budapest University of Technology and Economics 
@article{10_37236_2302,
     author = {G\'abor Simonyi and Claude Tardif and Ambrus Zsb\'an},
     title = {Colourful theorems and indices of homomorphism complexes},
     journal = {The electronic journal of combinatorics},
     year = {2013},
     volume = {20},
     number = {1},
     doi = {10.37236/2302},
     zbl = {1266.05041},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/2302/}
}
TY  - JOUR
AU  - Gábor Simonyi
AU  - Claude Tardif
AU  - Ambrus Zsbán
TI  - Colourful theorems and indices of homomorphism complexes
JO  - The electronic journal of combinatorics
PY  - 2013
VL  - 20
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/2302/
DO  - 10.37236/2302
ID  - 10_37236_2302
ER  - 
%0 Journal Article
%A Gábor Simonyi
%A Claude Tardif
%A Ambrus Zsbán
%T Colourful theorems and indices of homomorphism complexes
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/2302/
%R 10.37236/2302
%F 10_37236_2302
Gábor Simonyi; Claude Tardif; Ambrus Zsbán. Colourful theorems and indices of homomorphism complexes. The electronic journal of combinatorics, Tome 20 (2013) no. 1. doi: 10.37236/2302

Cité par Sources :