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...

Full description

Bibliographic Details
Main Authors: Berger, Eli, Choromanski, Krzysztof, Chudnovsky, Maria, Fox, Jacob, Loebl, Martin, Scott, Alex, Seymour, Paul, Thomasse, Stephan
Other Authors: Massachusetts Institute of Technology. Department of Mathematics
Format: Article
Language:en_US
Published: Elsevier 2015
Online Access:http://hdl.handle.net/1721.1/99446
Description
Summary: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.