Tournaments and colouring

Eli Berger, Krzysztof Choromanski, Maria Chudnovsky, Jacob Fox, Martin Loebl, Alex Scott, Paul Seymour, Stéphan Thomassé

Research output: Contribution to journalArticlepeer-review

37 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1-20
Number of pages20
JournalJournal of Combinatorial Theory. Series B
Volume103
Issue number1
DOIs
StatePublished - Jan 2013

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Colouring
  • Erdos-Hajnal conjecture
  • Tournament
  • Transitive

Fingerprint

Dive into the research topics of 'Tournaments and colouring'. Together they form a unique fingerprint.

Cite this