← All problems

Nguyen–Scott–Seymour cyclic-triangle conjecture

There exists an integer kk such that, for every tournament TT and every pair of disjoint vertex subsets X,Y⊆V(T)X,Y\subseteq V(T) with χ(T[X])≥k\chi(T[X])\ge k and χ(T[Y])≥k\chi(T[Y])\ge k, there are subsets A⊆XA\subseteq X and B⊆YB\subseteq Y such that ∣A∣=∣B∣=3|A|=|B|=3, both T[A]T[A] and T[B]T[B] are cyclic triangles, and either every edge between AA and BB is directed from AA to BB, or every edge between AA and BB is directed from BB to AA.

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

A new unrefereed preprint claims to disprove the conjecture, but the construction has not been independently assessed.

The conjecture of Nguyen, Scott, and Seymour asserts that two disjoint sufficiently high-chromatic parts of a tournament must contain cyclic triangles forming a complete pair.

October 2026 counterexample

Chen, van der Holst, and Wang claim that, for every positive integer dd, they construct a tournament with two parts of chromatic number at least dd but with no such pair of cyclic triangles. This would disprove the conjecture. The result is presented in an unrefereed preprint.

Current status (as of October 2026): The conjecture was previously recorded as open, but a 2026 preprint claims a counterexample; that claim remains unverified.

Sources

Solutions 0

No solutions have been posted yet.