Unavoidable Subtournaments in Tournaments with Large Chromatic Number

Ilhee Kim, Ringi Kim

Published 2018-04-13Version 1

For a set H of tournaments, we say H is heroic if every tournament, not containing any member of H as a subtournament, has bounded chromatic number. Berger et al. explicitly characterized all heroic sets containing one tournament. Motivated by this result, we study heroic sets containing two tournaments. We give a necessary condition for a set containing two tournaments to be heroic. We also construct infinitely many minimal heroic sets of size two.