PaperlayerView exact revision on arXiv

Source-linked AI summary

Clique Number of Tournaments II

Guillaume Aubian, Samuel Coulomb

arXiv:2609.07481v1math.COcs.DM

TL;DR

The paper addresses the complexity of deciding whether a tournament's directed clique number is at most a given threshold, a question raised by Nguyen, Scott, and Seymour. It studies this parameter through backward arcs in vertex orderings and proves the decision problem NP-complete for every k ≥ 3, contrasting with the corresponding fixed-k tractability in graphs.

  • Problem

    The complexity of deciding whether a tournament has directed clique number at most k was posed by Nguyen, Scott, and Seymour; the analogous fixed-k graph problem is polynomial-time solvable.

    Source: §1 · p. 2

  • Method

    The paper defines directed clique number through the minimum clique number of a backedge graph over vertex orderings.

    Source: §1 · p. 2

  • Results

    For every k ≥ 3, deciding whether a tournament has directed clique number at most k is NP-complete.

    Source: Theorem 1.1 · pp. 2, 4

  • Takeaways & Limitations

    The result contrasts with the polynomial-time solvability of the fixed-k clique-number decision problem for graphs.

    Source: §1 · p. 2, Theorem 3.1 · p. 4

    The paper leaves open whether the constant 100 can be improved, whether explicit small bounds for f(k) are available when k > 3, and whether such approximation algorithms exist for general digraphs.

    Source: Proposition 4.6 · p. 11

Abstract

from arXiv · show

The directed clique number $\vec{\omega}(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{\omega}(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 $\omega(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{\omega}(T) \leq 2$ from those with $\vec{\omega}(T) > 100$. We also study the tournament analogue of the Gy\'arf\'as--Sumner conjecture. We construct new $\vec{\chi}$-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{\chi}$-bounded. We then exhibit new tournaments that are not $\vec{\chi}$-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{\omega}$-critical and 4-$\vec{\omega}$-critical tournaments.

1 Introduction

The paper defines directed clique number through backward arcs in vertex orderings and studies complexity and chromatic structure in tournaments. It proves NP-completeness for every fixed threshold k ≥ 3 and reports results on approximation, χ-bounding classes, and critical tournaments.

1 Introduction

  • The directed clique number is defined using the minimum clique number of a backedge graph over vertex orderings.A backedge graph retains arcs that point backward in the chosen ordering; acyclic digraphs have an ordering with no backedges.Source: §1 · p. 2
  • Every ordered graph is the backedge graph of a unique tournament, linking ordered-graph structures to tournament study.A tournament is an orientation of a complete graph.Source: §1 · p. 2

Theorem 1.1

  • For every k ≥ 3, deciding whether a tournament has directed clique number at most k is NP-complete.This answers the complexity question posed by Nguyen, Scott, and Seymour.Source: Theorem 1.1 · p. 2, §1 · p. 2
  • A polynomial-time algorithm distinguishes tournaments with directed clique number at most 2 from those with directed clique number greater than 100.For an input tournament with directed clique number at most 2, the algorithm computes an ordering whose backedge graph has clique number at most 100.Source: Theorem 1.1 · p. 2

Conjecture 1.2 (Gyárfás [19] & Sumner [33])

  • The tournament work extends a graph-theoretic question about bounding chromatic number by clique number to the directed setting.For graphs, the paper notes that clique number does not generally bound chromatic number; the Gyárfás–Sumner conjecture concerns which substructures must occur in such graphs.Source: Theorem 1.1 · p. 2, §1 · p. 2
  • The paper establishes new directed-chromatic-bounding tournaments and proves that every class of tournaments with bounded twin-width is directed-chromatic-bounded.This confirms a conjecture of Aboulker, Aubian, Charbit, and Lopes.Source: Conjecture 1.2 (Gyárfás [19] & Sumner… · p. 3
  • New tournaments disprove the conjectured converse to the forest condition for directed-chromatic-bounding tournaments and two conjectures of Kim.Aboulker, Aubian, Charbit, and Lopes had shown that every directed-chromatic-bounding tournament has a backedge graph that is a forest.Source: Conjecture 1.2 (Gyárfás [19] & Sumner… · pp. 2–3
  • The paper presents infinite families of 3-directed-clique-critical and 4-directed-clique-critical tournaments.The families were found with Aboulker and Charbit.Source: Conjecture 1.2 (Gyárfás [19] & Sumner… · p. 3

2 Definitions and Notations

This section sets notation for ordered graphs, digraphs, backedge graphs, and tournament classes. It defines the dichromatic number through acyclic vertex partitions and supplies the vocabulary used for directed clique and directed chromatic arguments.

Ordered graphs

  • The section defines ordered graphs by a vertex ordering and treats their chromatic and clique numbers as those of the underlying graph.It defines induced ordered subgraphs by preserving both the order and adjacency relations.Source: §2 · p. 3

Backedge graphs

  • A backedge graph records an undirected edge for each arc that points backward in a chosen vertex ordering.The ordering places a backward arc's head before its tail.Source: §2 · p. 3

Dicolouring and directed clique number

  • A k-dicolouring partitions a digraph into k acyclic vertex sets, and the dichromatic number is the least such k.The section also describes a dicolouring as assigning colours so that each colour class induces an acyclic subdigraph.Source: §2 · p. 3

Tournaments

  • A tournament is an orientation of a complete graph, with exactly one arc between every pair of vertices.A tournament is transitive when it is acyclic.Source: §2 · p. 4
  • For a tournament class, directed-chromatic-boundedness bounds dichromatic number by a function of directed clique number; a tournament is bounding when its free class has that property.The section also defines composition of three tournaments using cyclic arcs between them.Source: §2 · p. 4

3 Computing the Clique Number of Tournaments is NP-complete

For every fixed k ≥ 3, deciding whether a tournament has directed clique number at most k is NP-complete. The proof builds variable and clause gadgets for a 3-SAT reduction, supported by tools that control orderings and increase directed clique number.

Theorem 1.1

  • For every k ≥ 3, deciding whether a tournament T has directed clique number at most k is NP-complete.The result contrasts with the undirected fixed-k decision problem, which is polynomial-time solvable.Source: Theorem 1.1 · p. 4, Theorem 3.1 · p. 4
  • For k = 1 the decision problem is in P, while the case k = 2 remains open.Source: Theorem 1.1 · p. 4

Theorem 3.1

  • Computing the directed clique number of tournaments is NP-hard.The paper describes this optimization hardness as an expected analogue of the undirected case.Source: Theorem 3.1 · p. 4

Definition 3.3

  • The construction tools force vertex orderings and raise a tournament's directed clique number while preserving specified optimal orderings.If the starting digraph has directed clique number k − 1, Lemma 3.5 constructs one with value k and characterizes its optimal orderings.Source: Definition 3.3 · p. 5

3.2 Gadgets and NP-completeness

  • The reduction uses variable gadgets whose two designated arcs have exactly one forward in every optimal ordering, encoding the variable's truth value.Clause gadgets have directed clique number 3, force at least one of three designated arcs backward, and permit any pair of those arcs to be forward in an optimal ordering.Source: §3.2 · pp. 5–7
  • The reduction constructs a tournament with directed clique number 3 exactly when the 3-SAT formula is satisfiable, proving NP-completeness for the threshold 3.The paper extends this result to every larger k using Lemma 3.5.Source: §3.2 · pp. 8–9

4 Approximation Algorithms

The section develops structural certificates for large directed clique number and polynomial-time algorithms that distinguish low directed clique number from larger values. For tournaments with directed clique number at most 2, it gives an ordering whose backedge graph has clique number at most 100.

Theorem 4.1 (Crew, Fan, Koerts, Moore, & Spirkl [13])

  • Every tournament with sufficiently large directed clique number contains a subtournament from one of two families, A_n or D_n, whose directed clique numbers grow with n.Excluding members of both families characterizes tournament classes with bounded directed clique number.Source: Theorem 4.1 (Crew, Fan, Koerts, Moore,… · p. 9, §4 · p. 9

Corollary 4.2 (Crew et al. [13])

  • For every k, sufficiently large tournament directed clique number guarantees a subtournament of bounded size with directed clique number at least k.The corresponding bounded-size guarantee does not hold for digraphs in general.Source: Corollary 4.2 (Crew et al. [13]) · p. 9

Proposition 4.3

  • For every pair k, ℓ, there is a digraph with directed clique number at least k and no directed cycle of length at most ℓ.The construction uses recursively substituted copies around a directed cycle of length ℓ + 1.Source: Proposition 4.3 · pp. 9–10

Corollary 4.4

  • For each k ≥ 3, a polynomial-time algorithm certifies either directed clique number at least k or less than a threshold f(k).It searches for fixed-size copies of A_N(k) or D_N(k); finding one certifies the lower bound, while their absence gives the threshold certificate.Source: Corollary 4.4 · p. 10

Proposition 4.5 (Klingelhoefer & Newman [24])

  • A polynomial-time 10-dicolouring algorithm is available for tournaments with dichromatic number at most 2, but replacing 10 by 3 is impossible unless P = NP.Whether an analogous algorithm exists for general digraphs is open.Source: Proposition 4.5 (Klingelhoefer &… · p. 10

Proposition 4.6

  • 100 is an upper bound on the backedge-graph clique number of an ordering computed in polynomial time for every tournament with directed clique number at most 2.The proof first constructs a 50-dicolouring and then shows each colour class contributes at most two vertices to any backedge-graph clique.Source: Proposition 4.6 · pp. 10–11
  • The approximation algorithm applies to tournaments; whether such algorithms exist for general digraphs remains open.The authors also leave open improving the bound 100 or obtaining small explicit f(k) values for k > 3.Source: Proposition 4.6 · p. 11

5 The Gyárfás-Sumner Conjecture for Tournaments

This section studies dichromatic-number bounds for tournaments through the Gyárfás–Sumner framework. It develops new χ-bounding results, including for U5-free tournaments and ordered graphs M_n.

5 The Gyárfás-Sumner Conjecture for Tournaments

  • The section constructs new χ-bounding tournaments and non-χ-bounding tournaments with a forest backedge graph, addressing conjectures of Aboulker, Aubian, Charbit, and Lopes and Kim.The section also aims to establish the conjecture that every bounded-twin-width class of tournaments is χ-bounded.Source: §5 · p. 11

Proposition 5.1 (Aboulker, Aubian, Charbit, & Lopes [1])

Theorem 5.2 (Liu [26])

  • Every U5-free tournament is χ-bounded: its prime members are 2-dicolourable, and substitution preserves χ-boundedness.Prime U5-free tournaments have the structural characterization stated in Liu [26].Source: Theorem 5.2 (Liu [26]) · p. 12

Corollary 5.3

  • For every n ≥ 4, the ordered graph M_n, with edges v1v_(n−1) and v2v_n, is χ-bounding.M4 is the previously established four-vertex case; this result extends it to all n ≥ 4.Source: Corollary 5.3 · p. 12

Theorem 5.4 (Scott & Seymour [31])

This section uses structural graph results and Ramsey theory to establish χ-boundedness for ordered graphs M_n. Its proof finds M_n inside sufficiently structured ordered bananas.

Theorem 5.4 (Scott & Seymour [31])

  • For all k, ℓ, m, sufficiently high chromatic number forces a clique of size k or an induced (ℓ, m)-banana.An (ℓ, m)-banana consists of m internally disjoint paths of length at least ℓ with the same endpoints.Source: Theorem 5.4 (Scott & Seymour [31]) · p. 12

Theorem 5.5 (Ramsey [30])

  • For every positive n and c, a sufficiently large clique with c-edge-coloured edges contains an n-vertex monochromatic clique.The proof applies this result to a three-colouring of pairs of paths.Source: Theorem 5.5 (Ramsey [30]) · p. 12

Theorem 5.6

  • The proof colours path pairs by their ordering relation and extracts M_n from a monochromatic set of 5n paths.The three cases are paths that are next to, surround, or cross one another; the resulting M_n is an induced ordered subgraph.Source: Theorem 5.6 · p. 12

Theorem 5.7

Theorem 5.7 proves that every class of tournaments with bounded twin-width is χ-bounded. The proof obtains this bound through a forbidden tournament whose backedge graph is a matching.

Theorem 5.7

  • Every class of tournaments with bounded twin-width is χ-bounded.The proof places such a class inside Forb(H) for a χ-bounding tournament H whose backedge graph is a matching.Source: Theorem 5.7 · p. 13
  • Whether the bounded-twin-width conclusion extends to digraph classes is open; polynomial χ-boundedness for tournament classes is also posed as a question.The undirected analogue is polynomially χ-bounded.Source: Theorem 5.7 · p. 13

5.2 Non −→ χ -bounding tournaments

The section constructs tournaments with bounded directed clique number and large dichromatic number, then derives a necessary condition for a tournament to be directed-chromatic-bounding. That condition leads to the notion of incomparable backedge graphs.

5.2 Non −→ χ -bounding tournaments

  • A graph of clique number 2 and chromatic number k yields a tournament with directed clique number 2 and dichromatic number at least k.The tournament is chosen to have the ordered graph as a backedge graph.Source: §5.2 · p. 14

Proposition 5.9 (Aboulker, Aubian, Charbit, & Lopes [1])

  • Every −→ χ-bounding tournament has a forest backedge graph, but the converse was conjectured by Aboulker, Aubian, Charbit, and Lopes [1].The section develops a stronger necessary condition using incomparable backedge graphs.Source: Proposition 5.9 (Aboulker, Aubian,… · p. 14
  • An (r−1, ⌊r/2⌋−1)-incomparable ordered graph has no cycle of length at most r.This links incomparability to girth and supports the necessary-condition argument.Source: Proposition 5.9 (Aboulker, Aubian,… · p. 14
  • Every −→ χ-bounding tournament must have a backedge graph that is (r,s)-incomparable for every positive r and s.The argument uses ordered graphs with clique number 2 and unbounded chromatic number, together with the backedge-graph construction.Source: Proposition 5.9 (Aboulker, Aubian,… · p. 14

Proposition 5.12 (Kim & Kim [23])

The section uses recursively constructed triangle-free graphs with high chromatic number to obtain tournaments with directed clique number 2 and large dichromatic number. It also gives forest-backedge-graph tournaments that are not directed-chromatic-bounding.

Proposition 5.12 (Kim & Kim [23])

  • An ordered graph is incomparable exactly when its vertices split into ordered parts whose cross-edges lie in different connected components and whose induced parts are incomparable.Source: Proposition 5.12 (Kim & Kim [23]) · p. 15
  • Six tournaments have a forest backedge graph but no incomparable backedge graph, contradicting the conjecture that every such forest tournament is −→ χ-bounding.Figure 9 represents these tournaments by their forest backedge graphs.Source: Proposition 5.12 (Kim & Kim [23]) · p. 15, Figure 9 · p. 15
  • The Blanche Descartes graphs B_k are triangle-free with chromatic number k, and their associated tournaments have directed clique number 2 and dichromatic number at least k.The tournament uses the recursively defined ordering of B_k as its backedge graph.Source: Proposition 5.12 (Kim & Kim [23]) · p. 15

Proposition 5.13

The section derives a partition property for directed-chromatic-bounding tournaments and uses its failure to identify further non-bounding examples. It also applies these examples to refute two conjectures of Kim.

Proposition 5.13

  • The partition requires A_0 to be transitive, with specified limits on arcs between A_0 and each other part.The provided conditions state that vertices outside A_0 have at most one arc to A_0, and vertices in A_0 have at most one arc from each A_i.Source: Proposition 5.13 · pp. 15–16
  • Some tournaments fail the partition property required of −→ χ-bounding tournaments and therefore are not −→ χ-bounding.The examples are represented in Figure 11.Source: Proposition 5.13 · pp. 15–16, Figure 11 · p. 16
  • The authors could not find further non-−→ χ-bounding tournaments using other constructions of triangle-free graphs with large chromatic number.Figure 12 shows the smallest tournaments for which this status remains open.Source: Proposition 5.13 · p. 16
  • A tournament T_2 satisfying Kim’s conjecture hypotheses, together with T_1 = D_3, yields a class Forb(T_1,T_2) with unbounded dichromatic number.The tournaments T_Bk contain neither T_1 nor T_2, contradicting the conjectured boundedness.Source: Proposition 5.13 · p. 16

Conjecture 5.14

The section proposes a characterization of directed-chromatic-bounding tournaments and discusses directed-clique-critical tournaments. It establishes an infinite family of 3-directed-clique-critical tournaments and relates NP-hardness to the existence of infinitely many 4-critical tournaments.

Conjecture 5.14

  • A tournament is −→ χ-bounding if and only if it has a backedge graph that is χ-bounding.The section presents this as a proposed characterization.Source: Conjecture 5.14 · p. 16
  • For k ≥ 4, NP-hardness implies infinitely many k-−→ ω-critical tournaments unless P=NP.If there were only finitely many, testing for any of them would decide whether a tournament has directed clique number at least k in polynomial time.Source: Conjecture 5.14 · p. 17
  • The paper presents constructions of two infinite families of 3- and 4-−→ ω-critical tournaments.The one-vertex tournament and directed triangle are the only 1- and 2-−→ ω-critical tournaments, respectively.Source: Conjecture 5.14 · p. 17

Proposition 6.1

  • For every n ≥ 3, T_{2n+1} is 3-−→ ω-critical.The proof shows its directed clique number is at least 3, while deleting any vertex leaves directed clique number at most 2.Source: Proposition 6.1 · p. 17

Proposition 6.2

For every n ≥ 3, Δ(T_{2n+1}, T_{2n+1}, T_{2n+1}) is 4-directed-clique-critical. The construction generalizes to (k + 1)-critical tournaments from k-directed-chromatic-critical tournaments, though existence of the needed inputs is unknown for k ≥ 4.

Proposition 6.2

  • For every n ≥ 3, Δ(T_{2n+1}, T_{2n+1}, T_{2n+1}) is 4-directed-clique-critical.Every vertex deletion leaves directed clique number 3.Source: Proposition 6.2 · pp. 17–18
  • Any ordering starts with a vertex in one component, which is adjacent in the backedge graph to every vertex of another component of directed clique number 3.This forces the full tournament's directed clique number to be at least 4.Source: Proposition 6.2 · p. 17
  • The construction generalizes to (k + 1)-directed-clique-critical tournaments from k-directed-chromatic-critical tournaments with directed clique number k.The authors do not know whether such input tournaments exist for k ≥ 4.Source: Proposition 6.2 · p. 18

7 Open Problems

The section collects open questions on the complexity and approximation of directed clique number, directed chromatic boundedness, critical tournaments, and related tournament structure.

Problem 7.1

  • The complexity of deciding whether a tournament has directed clique number at most 2 remains open, as does whether general digraphs admit polynomial-time approximation algorithms.For tournaments, the k = 2 case is equivalent to deciding whether a digraph has a triangle-free backedge graph.Source: Problem 7.1 · p. 18, §7 · p. 18, Problem 7.2 · p. 18

Problem 7.3 (Gutowski & Rams [18])

Problem 7.4 (Aboulker, Aubian, Charbit, & Lopes [1])

Problem 7.5

  • Are tournament classes with bounded twin-width polynomially directed-χ-bounded, and does directed-χ-boundedness extend to bounded-twin-width digraph classes?The paper establishes directed-χ-boundedness for bounded-twin-width tournament classes, but asks about these stronger versions.Source: Problem 7.5 · p. 18, Problem 7.4 (Aboulker, Aubian,… · p. 18
  • A possible characterization of directed-χ-bounding tournaments is proposed in Conjecture 5.14, after counterexamples refute the forest-based tournament analogue of Gyárfás–Sumner.The proposed characterization's content is not given in this passage.Source: Problem 7.5 · p. 18

Problem 7.6 (Aboulker, Aubian, Charbit, & Lopes [1])

Problem 7.7 (Kim [22])

Problems 7.8–7.9

Loading 2609.07481v1…