Clique Number of Tournaments

Abstract

Given a digraph $D$ together with an ordering $\prec$ of its vertices, the backedge graph of $D$ with respect to $\prec$ is the undirected graph $D^{\prec}$ with the same vertex set as $D$, where $xy \in E(D^{\prec})$ if $xy \in A(D)$ and $y \prec 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 $\overrightarrow{\chi}$-bounded classes of digraphs, which constitute the main topic of this paper, with a primary focus on tournaments. A class of tournaments is $\overrightarrow{\chi}$-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 $\overrightarrow{\chi}$-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 $\overrightarrow{\chi}$-bounded, then so is its closure under substitution. We also explore the relationship between $\overrightarrow{\chi}$-bounded classes of tournaments and certain conjectures on tournaments. We prove that a $\overrightarrow{\chi}$-bounded class of tournaments satisfies the $BIG \Rightarrow BIG$ Conjecture, and that a polynomially $\overrightarrow{\chi}$-bounded class of tournaments satisfies the (tournament) Erdős-Hajnal Conjecture.