← All problems

Erdős–Gyárfás balanced-coloring conjecture

For every integer r≥3r\ge 3, every edge-coloring c:E(Kr2+1)→{1,…,r}c:E(K_{r^2+1})\to\{1,\ldots,r\} contains a set S⊆V(Kr2+1)S\subseteq V(K_{r^2+1}) with ∣S∣=r+1|S|=r+1 and a color i∈{1,…,r}i\in\{1,\ldots,r\} such that i∉{c(e):e∈E(Kr2+1[S])}i\notin\{c(e):e\in E(K_{r^2+1}[S])\}. Equivalently, among every rr-coloring of Kr2+1K_{r^2+1}, some r+1r+1 vertices induce a subgraph whose edges do not use all rr colors.

Equivalent formulations
  1. For every integer r≥3r\ge 3, the complete graph Kr2+1K_{r^2+1} admits no balanced rr-coloring, where an edge-coloring of a complete graph with rr colors is balanced if the edges induced by every set of r+1r+1 vertices use all rr colors.

    source: Erdős–Gyárfás Balanced Five-Colorings

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

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 rr-coloring of Kr2+1K_{r^2+1} should contain r+1r+1 vertices whose induced subgraph omits a color, for r≥3r\ge 3. It is equivalent to identifying the smallest order admitting a balanced rr-coloring.

Known results

  • The conjecture was known for r=3r=3 and r=4r=4 by 2013; the historical account attributes the formulation to Erdős and Gyárfás (1999).

October 2026 claimed r=5r=5 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 r=3r=3 and r=4r=4 are established, while the claimed r=5r=5 result is unverified and the general conjecture remains open.

Sources

Solutions 0

No solutions have been posted yet.