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

Research log for issue #45. The general conjecture remains open.

For every integer r≥3r\ge3, an rr-edge-coloring of the complete graph on r2+1r^2+1 vertices must have r+1r+1 vertices whose induced edges omit a color. Equivalently, its color graphs cannot all have independence number at most rr.

Literature

  • Erdős and Gyárfás, Conjecture 1 and p. 80 pose the statement, prove the three- and four-color cases, and construct a sharp r2r^2-vertex example from an affine plane when one exists.
  • Gyárfás, §2.2 revisits the problem and the related threshold where the tested subset size is the ceiling of the number of vertices divided by rr.
  • Xia and Szeider give a proof of the five-color case using certified computations. The Erdős Problems wiki indexes other fixed-case claims and reviews, including a reported gap in the seven-through-nine-color manuscripts it reviewed. These claims do not cover the general statement.
  • The Erdős Problems wiki research record, §4 already excludes rr disjoint monochromatic rr-cliques of a single color. This excludes any extension of the affine-plane construction that keeps the old line cliques. The same research record gives lower bounds on how many old edges must be recolored.
  • Clique residue and affine repair, §3 uses the independent-transversal obstruction on a prescribed set of disjoint full cliques. The useful threshold is an independent set of size r−t+1r-t+1 outside tt cliques.
  • OutBlade's notes, §2 bound the product of fractional clique cover numbers in two colors.

The general claim was checked against the original paper, the coauthor's retrospective, recent arXiv results, the problem archive and its linked research reports, and public code repositories in November 2026. No proof or counterexample for the full conjecture was found.

When the residue forces complete cross matchings

Suppose a hypothetical balanced coloring contains t≥2t\ge2 vertex-disjoint cliques of order rr in color ii. Let RR be the other vertices and let ss be the independence number of their color-ii graph. If s≥r−t+2s\ge r-t+2, the color-ii graph on the packed cliques is a rook graph. In other words, between every two packed cliques there is a perfect matching, and the matchings identify the vertices consistently across all cliques. For any maximum independent set SS in RR, each vertex of SS is adjacent in color ii to precisely one of the resulting columns, and those columns are distinct.

Proof

Write Q1,…,QtQ_1,\ldots,Q_t for the cliques. Every external vertex has at most one edge of color ii to a given QjQ_j, since the other r−1r-1 colors must each occur in the rr edges into that clique. In particular, the edges of color ii between any two cliques form a matching.

The transversal lemma in the prior packing argument says that if m≥2m\ge2 parts have size at least m−1m-1, the edges between any two form a matching, and there is no independent transversal, then all parts have size m−1m-1 and the matchings are perfect and consistent. For m=1m=1, the no-transversal condition simply requires the only part to be empty.

Fix SS of size ss, and set m=r+1−sm=r+1-s. In every QjQ_j the vertices having no neighbor in SS form a list of size at least r−s=m−1r-s=m-1. For any mm of the tt lists, an independent transversal would extend SS to an independent set of order r+1r+1. The lemma forces all lists to have size m−1m-1. Thus every member of SS has one neighbor in each QjQ_j and these neighbors are distinct in each clique. The lists are joined by perfect matchings if m≥2m\ge2. They are consistent when m≥3m\ge3 by applying the lemma to a selection containing any given three lists. When m≤2m\le2 the lists have size at most one and consistency is immediate.

Now remove one vertex uu from SS. Each list gains exactly one vertex, the neighbor of uu. Because s≥r−t+2s\ge r-t+2, we have m+1≤tm+1\le t. Applying the lemma to any m+1m+1 enlarged lists gives a perfect matching between each pair. Every old list vertex already has its old mate, so the two newly available vertices must be matched to each other. Doing this for every uu proves the assertion about the full matchings and about the corresponding columns.

Edge consequence

The packed cliques, their cross matchings, and edges from SS into the cliques force the following lower bound, with the last term counting edges of color ii entirely within RR.

e(Gi)≥t(r2)+r(t2)+st+e(Gi[R]).e(G_i) \ge t\binom r2+r\binom t2+st+e(G_i[R]).

In particular, if r≥13r\ge13 and t≥2r/3t\ge2r/3, the two clique terms alone exceed the average color budget r(r2+1)/2r(r^2+1)/2. In that range a sparsest color with such a packing must therefore satisfy α(Gi[R])≤r−t+1\alpha(G_i[R])\le r-t+1. This comparison uses r2−12r−9>0r^2-12r-9>0 for r≥13r\ge13. It complements the prior bound at s=r−t+1s=r-t+1, which forces t−1t-1 matched columns across the tt cliques.

The argument assumes a large packing of monochromatic cliques. The arbitrary coloring case includes color graphs for which no such packing has been established.