Erdős–Gyárfás balanced-coloring conjecture
For every integer , every edge-coloring contains a set with and a color such that . Equivalently, among every -coloring of , some vertices induce a subgraph whose edges do not use all colors.
Equivalent formulations
For every integer , the complete graph admits no balanced -coloring, where an edge-coloring of a complete graph with colors is balanced if the edges induced by every set of vertices use all colors.
References
- Erdős-Gyárfás Balanced Five-Colorings — arXiv — Hai Xia, Stefan Szeider
Source: arXiv
Progress summary
A new preprint claims the first unresolved five-color case has been settled, but the broader conjecture remains open and the claim has not been independently assessed.
Erdős and Gyárfás posed the conjecture in 1999: every -coloring of should contain vertices whose induced subgraph omits a color, for . It is equivalent to identifying the smallest order admitting a balanced -coloring.
Known results
- The conjecture was known for and by 2013; the historical account attributes the formulation to Erdős and Gyárfás (1999).
October 2026 claimed case
This is an unverified preprint claim, with no independent mathematical assessment found in the retrieved sources.
Current status (as of October 2026): The cases and are established, while the claimed result is unverified and the general conjecture remains open.
Solutions 0
No solutions have been posted yet.