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

About 1 year old · traced to

Let GG be a finite simple graph. For disjoint vertex sets A,B⊆V(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 ℓ,w≥1\ell,w\ge1 and every forest TT, there exists k≥2k\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.

References

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.