The good ordering conjecture for tournament twin-width and clique number

About 3 years old · traced to

For a tournament TT and an ordering ≺\prec of V(T)V(T), let T≺T^{\prec} be its backedge graph. A BST-ordering is the ordering associated with a binary search tree satisfying the tournament-neighbourhood conditions described in the paper. The good ordering conjecture. There exists a function ff such that, for every tournament TT, there exists an ordering ≺∗\prec^* of V(T)V(T) such that

ω(T≺∗)≤f(ω→⁡(T))andtww(T,≺∗)≤f(tww(T)).\omega(T^{\prec^*})\leq f(\operatorname{\overrightarrow{\omega}}(T))\quad\text{and}\quad tww(T,\prec^*)\leq f(tww(T)).

If true, this would imply the bounded twin-width conjecture; the paper notes that BST-orderings are natural candidates because they already provide the required twin-width bound, leaving the backedge-graph clique bound open.

References

Primary source

Pierre Aboulker, Guillaume Aubian, Pierre Charbit and Raul Lopes, “Clique number of tournaments”, arXiv:2310.04265 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.