TOPICS
Search

Directed Clique Number

The directed clique number of an oriented graph D is

omega^->(D)=min_(≺)omega(D_≺),

where ≺ ranges over vertex orders and D_≺ is the undirected graph joining u and v whenever u≺v and D contains the arc v->u. Thus D_≺ records backward arcs, and omega denotes its ordinary clique number (Aboulker et al. 2026).

A nonempty acyclic digraph has directed clique number 1, while a cyclic triple has value 2. The directed clique number is at most the dichromatic number. For a tournament, this invariant generally differs from the clique number of the underlying complete graph.

Aboulker et al. (2026) note that this definition already occurs in Kim's (2013) thesis. Subsequent work includes Aubian and Coulomb's (2026) proof that deciding omega^->(T)<=k is NP-complete for every fixed integer k>=3 when T is a tournament.

See also

Clique Number, Dichromatic Number, Tournament

Explore with Wolfram|Alpha

References

Aboulker, P.; Aubian, G.; Charbit, P.; and Lopes, R. "Clique Number of Tournaments." Electron. J. Combin. 33, P3.56, 2026. https://doi.org/10.37236/12557.Aubian, G. and Coulomb, S. "Clique Number of Tournaments II." 7 Sep 2026. https://arxiv.org/abs/2609.07481.Kim, I. "On Containment Relations in Directed Graphs." PhD thesis. Princeton, NJ: Princeton University, 2013.

Cite this as:

Weisstein, Eric W. "Directed Clique Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/DirectedCliqueNumber.html

Subject classifications