The complete-pairs formulation of the Gyárfás–Sumner conjecture
The complete-pairs formulation of the Gyárfás–Sumner conjecture
Let be a finite simple graph. For disjoint vertex sets , call a complete pair if every possible edge between and is present. For a forest , call -free if it has no induced subgraph isomorphic to . Complete-pairs formulation. For every and every forest , there exists such that every -free graph with and contains a complete pair with . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.