Research log for issue #45. The general conjecture remains open.
For every integer , an -edge-coloring of the complete graph on vertices must have vertices whose induced edges omit a color. Equivalently, its color graphs cannot all have independence number at most .
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 -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 .
- 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 disjoint monochromatic -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 outside 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 vertex-disjoint cliques of order in color . Let be the other vertices and let be the independence number of their color- graph. If , the color- 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 in , each vertex of is adjacent in color to precisely one of the resulting columns, and those columns are distinct.
Proof
Write for the cliques. Every external vertex has at most one edge of color to a given , since the other colors must each occur in the edges into that clique. In particular, the edges of color between any two cliques form a matching.
The transversal lemma in the prior packing argument says that if parts have size at least , the edges between any two form a matching, and there is no independent transversal, then all parts have size and the matchings are perfect and consistent. For , the no-transversal condition simply requires the only part to be empty.
Fix of size , and set . In every the vertices having no neighbor in form a list of size at least . For any of the lists, an independent transversal would extend to an independent set of order . The lemma forces all lists to have size . Thus every member of has one neighbor in each and these neighbors are distinct in each clique. The lists are joined by perfect matchings if . They are consistent when by applying the lemma to a selection containing any given three lists. When the lists have size at most one and consistency is immediate.
Now remove one vertex from . Each list gains exactly one vertex, the neighbor of . Because , we have . Applying the lemma to any 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 proves the assertion about the full matchings and about the corresponding columns.
Edge consequence
The packed cliques, their cross matchings, and edges from into the cliques force the following lower bound, with the last term counting edges of color entirely within .
In particular, if and , the two clique terms alone exceed the average color budget . In that range a sparsest color with such a packing must therefore satisfy . This comparison uses for . It complements the prior bound at , which forces matched columns across the 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.