Clique Number of Tournaments II
Abstract
The directed clique number ω⃗(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 ≥ 3, deciding whether ω⃗(T) ≤ k is NP-complete. This answers a question of Nguyen, Scott, and Seymour, and contrasts with the classical undirected setting, where deciding whether ω(G) ≤ k is polynomial-time solvable for every fixed integer k. On the other hand, we give a polynomial-time algorithm distinguishing tournaments with ω⃗(T) ≤ 2 from those with ω⃗(T) > 100. We also study the tournament analogue of the Gyárfás--Sumner conjecture. We construct new χ⃗-bounding tournaments and thereby prove a conjecture of Aboulker, Aubian, Charbit, and Lopes stating that every class of tournaments with bounded twin-width is χ⃗-bounded. We then exhibit new tournaments that are not χ⃗-bounding, disproving another conjecture of Aboulker, Aubian, Charbit, and Lopes, as well as two conjectures of Kim. Finally, we present infinite families of 3-ω⃗-critical and 4-ω⃗-critical tournaments.
Related
- Cayley Tournaments Simultaneously Critical for the Clique and Dichromatic Numbers
- Digraphs of Large Girth and Dichromatic Number in Tournaments with Large Dichromatic Number
- Acyclic Dichromatic Number of Tournaments: these are the Champions
- The maximum number of Hamiltonian cycles in tournaments
- Fractional Dichromatic Number and Domination in Tournaments
BibTeX
@misc{aubian2026clique,
title = {{Clique Number of Tournaments II}},
author = {Guillaume Aubian and Samuel Coulomb},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.07481},
eprint = {2609.07481},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.07481},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Clique Number of Tournaments II
AU - Guillaume Aubian
AU - Samuel Coulomb
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.07481
UR - https://arxiv.org/abs/2609.07481
AB - The directed clique number ω⃗(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 ≥ 3, deciding whether ω⃗(T) ≤ k is NP-complete. This answers a question of Nguyen, Scott, and Seymour, and contrasts with the classical undirected setting, where deciding whether ω(G) ≤ k is polynomial-time solvable for every fixed integer k. On the other hand, we give a polynomial-time algorithm distinguishing tournaments with ω⃗(T) ≤ 2 from those with ω⃗(T) > 100. We also study the tournament analogue of the Gyárfás--Sumner conjecture. We construct new χ⃗-bounding tournaments and thereby prove a conjecture of Aboulker, Aubian, Charbit, and Lopes stating that every class of tournaments with bounded twin-width is χ⃗-bounded. We then exhibit new tournaments that are not χ⃗-bounding, disproving another conjecture of Aboulker, Aubian, Charbit, and Lopes, as well as two conjectures of Kim. Finally, we present infinite families of 3-ω⃗-critical and 4-ω⃗-critical tournaments.
ER -