×

zbMATH — the first resource for mathematics

Tournaments and colouring. (English) Zbl 1254.05064
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.

MSC:
05C20 Directed graphs (digraphs), tournaments
05C55 Generalized Ramsey theory
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI