Gyárfás’s monochromatic tree-cover conjecture
Follow the latest progress by email.
Can the vertices of every r-edge-colored complete graph be covered by r−1 monochromatic trees? Trees may overlap and single vertices count as trees; this covering question is distinct from partitioning into trees.
Why it matters and what counts as progress
Why it matters: Overlapping tree covers impose a weaker requirement than disjoint tree partitions, so partition counterexamples do not settle this conjecture.
What counts as progress: Prove the covering bound or construct colorings requiring r trees, including infinite families of color counts.
How the problem developed
- 1977 · Conjecture [1]
András Gyárfás Formulated the complete-graph conjecture: every r-edge-coloring can be covered by at most r−1 monochromatic connected subgraphs.
OpenAI A preprint reports intersecting r-partite hypergraphs violating the corresponding Ryser bound for infinitely many part counts; the cited equivalence transfers the claim to the tree-cover formulation.
AI contribution
A counterexample to Ryser's covering conjecture
For every sufficiently large prime s≡2 mod 3 and sufficiently large odd n depending on s, with r=s^n+1, the manuscript constructs an r-edge-colored complete graph requiring exactly r monochromatic trees to cover its vertices, even when trees may overlap and singletons count.
Sources
- D. West, Monochromatic coverings of edge-colored graphs
- András Gyárfás and Zoltán Király, Covering complete partite hypergraphs by monochromatic components
- OpenAI, Ryser counterexamples and Gyárfás corollary
- A counterexample to Ryser's covering conjecture
- OpenAI, Lean proof of the hypergraph premise
- OpenAI mathematics collection and provenance
Website timeline
Publication dates and editorial changes.
OpenAI reports counterexamples to Gyárfás’s tree-cover conjecture