Crossing tournaments are polynomially $\vecχ$-bounded
2026-08-10 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors discuss a special way to measure complexity in tournaments, called the clique number of backedge graphs, introduced by Aboulker and colleagues in 2023. They explore which groups of tournaments have their coloring complexity grow at most polynomially with this measure. Previous work showed this for tournaments that can be broken into a few simple parts, but some classes like crossing tournaments do not fit this pattern. The authors prove that crossing tournaments still behave nicely in terms of coloring complexity by using a technique from Davies and McCarty, but this doesn't extend to tournaments whose backedge graphs are chordal.
tournamentclique numberbackedge graphpolynomially $\\vec{χ}$-boundedcomparability digraphcrossing tournamentschordal graphgraph coloringDavies and McCarty method
Authors
Lila Crew, Xinyue Fan, Hidde Koerts, Benjamin Moore, Sophie Spirkl
Abstract
Given a tournament $T$, Aboulker, Aubian, Charbit, and Lopes (2023) defined its clique number $\vecω(T)$ as the minimum clique number of a backedge graph of $T$, and raised the question: Which classes of tournaments are polynomially $\vecχ$-bounded? Aboulker, Duron, Jacob, Kimbrough, Thomassé, and this work's authors (2026) showed that this holds for classes of tournaments whose arc sets may be written as the union of a bounded number of comparability digraphs. What about classes of tournaments that do not admit such a decomposition? The crossing tournaments of Nguyen, Scott, and Seymour (2025) are an example of such a class, as shown in the aforementioned 2026 work; we show that nonetheless crossing tournaments are polynomially $\vecχ$-bounded by adapting a method of Davies and McCarty (2021) and Davies (2022). We additionally show that we cannot extend this result for crossing tournaments to tournaments with chordal graphs as backedge graphs.