The complete-pairs formulation of the Gyárfás–Sumner conjecture

Let GG be a finite simple graph. For disjoint vertex sets A,BV(G)A,B\subseteq V(G), call (A,B)(A,B) a complete pair if every possible edge between AA and BB is present. For a forest TT, call GG TT-free if it has no induced subgraph isomorphic to TT. Complete-pairs formulation. For every ,w1\ell,w\ge1 and every forest TT, there exists k2k\ge2 such that every TT-free graph GG with χ(G)k\chi(G)\ge k and ω(G)w\omega(G)\le w contains a complete pair (A,B)(A,B) with χ(A),χ(B)\chi(A),\chi(B)\ge\ell. The source states that this is equivalent to the Gyárfás–Sumner conjecture, so it is another formulation of the same open problem.

Sources & referencesView supporting material

Primary source

Tung H. Nguyen, “On polynomially high-chromatic pure pairs”, arXiv:2504.21127 (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.