The Erdős-Gyárfás balanced coloring conjecture asserts that, for every integer 
, the complete graph 
has no balanced edge coloring with 
colors (Erdős and Gyárfás 1999). Equivalently, every assignment
of 
colors to its edges contains
vertices among which at
least one color is missing. The conjecture is problem 617
in the Erdős problems collection (Bloom 2026).
Erdős and Gyárfás (1999) proved the conjecture for 
and 
. Xia and Szeider (2026) proved the case 
, showing that 
has no balanced
edge coloring with five colors. Since 
has a balanced edge
coloring with five colors, it is the largest complete
graph admitting one. The general conjecture remains open.
Xia and Szeider (2026) report generative AI assistance with the Lean formalizations.
This conjecture is distinct from the Erdős-Gyárfás conjecture about cycles of power-of-two length.
