Clique Number of Tournaments

Given a digraph D together with an ordering of its vertices, the backedge graph of D with respect to is the undirected graph D^ with the same vertex set as D, where xy ∈ E(D^) if xy ∈ A(D) and y x. We introduce the notion of the clique number of a digraph D, defined as the minimum clique number over all backedge graphs of D. We investigate its relationship with the dichromatic number. In particular, this concept allows us to define χ-bounded classes of digraphs, which constitute the main topic of this paper, with a primary focus on tournaments. A class of tournaments is χ-bounded if, for every tournament in the class, its dichromatic number is bounded by a function of its clique number. We study for which tournaments H the class of H-free tournaments is χ-bounded, and prove in particular that H must have a backedge graph that is a forest. We prove that if a class of tournaments is χ-bounded, then so is its closure under substitution. We also explore the relationship between χ-bounded classes of tournaments and certain conjectures on tournaments. We prove that a χ-bounded class of tournaments satisfies the BIG ⇒ BIG Conjecture, and that a polynomially χ-bounded class of tournaments satisfies the (tournament) Erdős-Hajnal Conjecture.