Answers are grounded in this paper and cite their sources.
Study proves the six-color case of a conjecture in balanced coloring, indicating a key edge count implication.
We prove the six-color case of a conjecture of Erdős and Gyárfás: every six-coloring of the edges of K37 has seven vertices whose induced edges omit at least one color. For a fixed color, the counterex- ample hypothesis gives a graph in which every seven vertices span at most sixteen edges. We combine the Kang–Pikhurko extremal theorem with minimum-degree decompositions to prove clique lemmas on 18, 19, 24, and 25 vertices. These lemmas give a 97-edge lower bound for the relevant 31-vertex graphs and then contradict the edge count of a least color on 37 vertices. The proof is non-computational.
No takes yet. Share an insight, caveat, or question.
Robert Sneiderman (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: