Summary
This paper looks at a special way to measure 'cliques'—groups of connected points—in something called a tournament, which is like a round-robin competition but with directed relationships. The authors show that figuring out if the tournament's directed clique number is below a certain value is generally very hard (NP-complete) when that value is 3 or more. However, they provide a fast method for telling apart tournaments where this number is very small (2) from those where it is quite large (above 100). They also explore related ideas about colorings of tournaments and prove some mathematical predictions while disproving others. In addition, they introduce infinite series of tournaments that are critical with respect to their directed clique number.
tournamentdirected clique numberNP-completeclique numbergraph theorypolynomial-time algorithmGyárfás–Sumner conjecturetwin-widthcoloringcritical tournament
Abstract
The directed clique number $\vecω(T)$ of a tournament $T$ is the minimum, over all orderings of the vertices of $T$, of the clique number of the graph whose edges are the arcs that point backward with respect to the ordering. In this paper, we prove that, for every integer $k \geq 3$, deciding whether $\vecω(T) \leq k$ is NP-complete. This answers a question of Nguyen, Scott, and Seymour, and contrasts with the classical undirected setting, where deciding whether $ω(G) \leq k$ is polynomial-time solvable for every fixed integer $k$. On the other hand, we give a polynomial-time algorithm distinguishing tournaments with $\vecω(T) \leq 2$ from those with $\vecω(T) > 100$. We also study the tournament analogue of the Gyárfás--Sumner conjecture. We construct new $\vecχ$-bounding tournaments and thereby prove a conjecture of Aboulker, Aubian, Charbit, and Lopes stating that every class of tournaments with bounded twin-width is $\vecχ$-bounded. We then exhibit new tournaments that are not $\vecχ$-bounding, disproving another conjecture of Aboulker, Aubian, Charbit, and Lopes, as well as two conjectures of Kim. Finally, we present infinite families of 3-$\vecω$-critical and 4-$\vecω$-critical tournaments.