Originators: Berger et al. (presented by Kevin Milans - REGS 2011)
Definitions:
Let Tk denote the acyclic (or transitive) tournament on
k vertices. For a vertex v in a digraph, let
N+(v) denote the set of out-neighbors of v.
For S⊆V(G), let G[S] denote the subdigraph induced by
G. In a digraph G, a set S is acyclic if
G[S] contains no (directed) cycle. The chromatic number of a
tournament G, denoted χ(G) is the minimum size of a partition
of V(G) into acyclic sets. A tournament is strong if it contains
a path from each vertex to every other vertex.
A tournament H is a hero if there is a constant C such
that χ(G) ≤ C when G is a tournament that does not
contain H; we write this as "chromatic number of H-free
tournaments is bounded". We use Δ(F,G,H)
to denote the tournament obtained from disjoint tournaments F, G,
and H by orienting edges from F to G, from G to
H, and from H to F.
Background: Berger et al. [BCCFLSST] characterized heroes. They proved that H is a hero if and only if every strong component of H is a hero, and a strong tournament H is a hero if and only if H is &Delta(T1, H', Tk) or &Delta(T1, Tk, H') for some hero H'.
Conjecture [BCCFLSST]: For each k there is a constant C such that if G is a tournament in which χ(G[N+(v)]) ≤ k for each vertex v in G, then χ(G) ≤ C.
Comments: It is not hard to prove the conjecture when k = 1. The authors of [BCCFLSST] states that they were unable to establish the conjecture even for the case that k = 3; we do not know the status for k = 2.
Problem 1: Let H be the tournament Δ(T1, T3, T1). It follows from the characterization of Berger et al. that H is a hero. Determine the least C such that χ(G) ≤ C for every H-free tournament G.
Problem 2: Characterize the pairs {H1, H2} such tournaments containing neither H1 nor H2 have bounded chromatic number.
Problem 3: A tournament is defined by specifying a source vertex (the tail of the edge) for each pair of vertices. A k-tournament is defined by specifying a source for each k-set of vertices. A set S of vertices in a k-tournament is acyclic if S can be linearly ordered so that the source of each edge contained in S occurs before the other elements of the edge. With this generalization of the notion of acyclic sets to k-tournaments, the definitions of chromatic number and hero are the same as when k=2. Characterize the 3-tournaments that are heroes.
Comments: The listed problems were proposed by Milans, and very little is known about them.
References:
[BCCFLSST] E. Berger, K. Choromanski, M. Chudnovsky, J. Fox, M. Loebl, A. Scott,
P. Seymour, S. Thomassé. Tournaments and colouring, submitted,
2011+.