{"id":"arxiv/2609.07481","url":"https://arxiv.org/abs/2609.07481","tags":["math.CO","cs.DM"],"score":0,"title":"Clique Number of Tournaments II","domain":"math.CO","source":"arxiv","authors":["Guillaume Aubian","Samuel Coulomb"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-07","reactions":{}}