Acyclic Dichromatic Number of Tournaments: these are the Champions

Technical Summary: Acyclic Dichromatic Number of Tournaments

Problem Statement
This paper investigates the acyclic dichromatic number ($\vec{\chi}_a$) of oriented graphs, specifically within the context of tournaments. An acyclic $k$-dicolouring is a vertex partition into $k$ sets such that the subdigraph induced by any single part is acyclic, and the oriented bipartite graph between any two parts is also acyclic. The acyclic dichromatic number is the minimum $k$ required for such a partition.

The authors address two specific conjectures posed by Bang-Jensen, Picasarri-Arrieta, and Yeo [4]:

1. Characterization of Champions: Identifying which tournaments $H$ are "champions" (analogous to "heroes" in standard dichromatic number theory), meaning that every $H$-free tournament has a bounded acyclic dichromatic number.
2. Local-to-Global Property: Determining whether the acyclic dichromatic number of a tournament is bounded by a function of the maximum acyclic dichromatic number of the out-neighborhoods of its vertices.

Methodology
The paper employs structural graph theory and Ramsey-type arguments to establish bounds on the acyclic dichromatic number.

• Dimatchings: A central tool introduced is the dimatching, defined as a set of pairwise disjoint arcs $\{a_1b_1, \dots, a_kb_k\}$ such that $a_i \to b_j$ if $i=j$ and $a_i \leftarrow b_j$ if $i \neq j$. The authors leverage a result by Bang-Jensen et al. [4] stating that the existence of a large dimatching implies a high acyclic dichromatic number.
• Ramsey Theory: The proof utilizes the Erdős-Moser theorem [8] regarding the existence of transitive subtournaments in large tournaments to locate specific structural configurations (specifically, the tournament $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$) within tournaments containing large dimatchings.
• Reduction to Bipartite Graphs: To prove the existence of large dimatchings in tournaments with high acyclic dichromatic number, the authors reduce the problem to properties of bipartite graphs. They utilize a result by Atminas [2] concerning induced matchings and co-matchings in bipartite graphs. Specifically, they relate the acyclic dichromatic number of a bipartite tournament to the absence of induced $2K_2$ (induced matchings of size 2) in the underlying undirected bipartite graph.
• Recursive Partitioning: The proofs involve decomposing tournaments into transitive sets and analyzing the interactions between these sets using corollaries derived from Lemma 9, which bounds the acyclic dichromatic number of a digraph based on its induced subdigraphs.

Key Contributions and Results

1. Confirmation of the Champion Conjecture (Theorem 3):
   The authors prove that a tournament $H$ is a champion if and only if it is isomorphic to a subtournament of $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$ for some integer $k \ge 1$.

   • Mechanism: They demonstrate that any tournament with a sufficiently large dimatching must contain a subtournament isomorphic to $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$. Since large dimatchings force a high acyclic dichromatic number, any tournament avoiding this specific structure must have a bounded acyclic dichromatic number.

2. Existence of Dimatchings (Theorem 4):
   The paper establishes a function $f: \mathbb{N} \to \mathbb{N}$ such that every tournament with an acyclic dichromatic number at least $f(k)$ contains a dimatching of size $k$.

   • Mechanism: This result relies on Atminas' theorem [2] regarding bipartite graphs. By showing that if a tournament lacks a large dimatching, its structure can be partitioned into a bounded number of transitive sets with specific bipartite interactions, the authors bound the acyclic dichromatic number.

3. Confirmation of the Local-to-Global Property (Theorem 5):
   The authors prove the existence of a function $g: \mathbb{N} \to \mathbb{N}$ such that for any tournament $T$, $\vec{\chi}_a(T) \le \max_{v \in V(T)} g(\vec{\chi}_a(v^+))$.

   • Mechanism: This is derived as a consequence of Theorem 4. If a tournament has a large acyclic dichromatic number, it contains a large dimatching. The structure of this dimatching ensures that the out-neighborhood of certain vertices contains a large dimatching, thereby forcing a high acyclic dichromatic number in the local neighborhood.

Significance and Claims
The paper confirms two conjectures by Bang-Jensen, Picasarri-Arrieta, and Yeo [4], thereby completing the characterization of "champions" for the acyclic dichromatic number and establishing its local-to-global property.

The authors note that while the forward implication of the champion characterization (that champions must have the specific form) was previously known, the converse (that tournaments of this form are indeed champions) is the novel contribution of this work. Furthermore, the paper provides an alternative proof for Theorem 3 in the appendix that does not rely on Theorem 4 or Atminas' result, which the authors suggest yields better upper bounds and may be of independent interest for future research.

The work bridges the gap between the well-understood dichromatic number (where "heroes" are characterized by a specific recursive structure) and the more restrictive acyclic dichromatic number, showing that while the structures differ, the fundamental properties of boundedness and locality hold for both parameters in tournaments.