Tournaments and colouring
A tournament is a complete graph with its edges directed, and colouring a tournament means partitioning its vertex set into transitive subtournaments. For some tournaments H there exists c such that every tournament not containing H as a subtournament has chromatic number at most c (we call such a t...
| Main Authors: | , , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Elsevier
2015
|
| Online Access: | http://hdl.handle.net/1721.1/99446 |
| _version_ | 1826208305284907008 |
|---|---|
| author | Berger, Eli Choromanski, Krzysztof Chudnovsky, Maria Fox, Jacob Loebl, Martin Scott, Alex Seymour, Paul Thomasse, Stephan |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Berger, Eli Choromanski, Krzysztof Chudnovsky, Maria Fox, Jacob Loebl, Martin Scott, Alex Seymour, Paul Thomasse, Stephan |
| author_sort | Berger, Eli |
| collection | MIT |
| description | A tournament is a complete graph with its edges directed, and colouring a tournament means partitioning its vertex set into transitive subtournaments. For some tournaments H there exists c such that every tournament not containing H as a subtournament has chromatic number at most c (we call such a tournament H a hero); for instance, all tournaments with at most four vertices are heroes. In this paper we explicitly describe all heroes. |
| first_indexed | 2024-09-23T14:03:42Z |
| format | Article |
| id | mit-1721.1/99446 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:03:42Z |
| publishDate | 2015 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | mit-1721.1/994462022-09-28T18:01:41Z Tournaments and colouring Berger, Eli Choromanski, Krzysztof Chudnovsky, Maria Fox, Jacob Loebl, Martin Scott, Alex Seymour, Paul Thomasse, Stephan Massachusetts Institute of Technology. Department of Mathematics Fox, Jacob A tournament is a complete graph with its edges directed, and colouring a tournament means partitioning its vertex set into transitive subtournaments. For some tournaments H there exists c such that every tournament not containing H as a subtournament has chromatic number at most c (we call such a tournament H a hero); for instance, all tournaments with at most four vertices are heroes. In this paper we explicitly describe all heroes. Simons Foundation (Fellowship) 2015-10-26T12:04:11Z 2015-10-26T12:04:11Z 2012-08 2011-01 Article http://purl.org/eprint/type/JournalArticle 00958956 1096-0902 http://hdl.handle.net/1721.1/99446 Berger, Eli, Krzysztof Choromanski, Maria Chudnovsky, Jacob Fox, Martin Loebl, Alex Scott, Paul Seymour, and Stephan Thomasse. “Tournaments and Colouring.” Journal of Combinatorial Theory, Series B 103, no. 1 (January 2013): 1–20. en_US http://dx.doi.org/10.1016/j.jctb.2012.08.003 Journal of Combinatorial Theory, Series B Creative Commons Attribution-Noncommercial-NoDerivatives http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier OAPOT |
| spellingShingle | Berger, Eli Choromanski, Krzysztof Chudnovsky, Maria Fox, Jacob Loebl, Martin Scott, Alex Seymour, Paul Thomasse, Stephan Tournaments and colouring |
| title | Tournaments and colouring |
| title_full | Tournaments and colouring |
| title_fullStr | Tournaments and colouring |
| title_full_unstemmed | Tournaments and colouring |
| title_short | Tournaments and colouring |
| title_sort | tournaments and colouring |
| url | http://hdl.handle.net/1721.1/99446 |
| work_keys_str_mv | AT bergereli tournamentsandcolouring AT choromanskikrzysztof tournamentsandcolouring AT chudnovskymaria tournamentsandcolouring AT foxjacob tournamentsandcolouring AT loeblmartin tournamentsandcolouring AT scottalex tournamentsandcolouring AT seymourpaul tournamentsandcolouring AT thomassestephan tournamentsandcolouring |