Erdős Problem #811
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory, ramsey theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
A completely balanced m-edge-coloring of K_n, where m=e(H) and n≡1 (mod m), has exactly (n-1)/m edges of EACH color at EACH vertex. Classify those graphs H for which every such balanced coloring for all sufficiently large eligible n contains a RAINBOW H (all m edges with distinct colors). The classification remains OPEN; the assertion that EVERY H works has been DISPROVED.
The category of target graphs with the balanced rainbow property remains to be classified. In particular, 2023 published work constructs balanced six-colorings of complete graphs on 13^k vertices with no rainbow K4. Thus universal success for every target is false, while the C6 and general classification questions remain live.
A small example
For n=7 and m=3, color edge {i,j} of K7 by cyclic distance min((i-j) mod7,(j-i) mod7) in {1,2,3}. Each vertex sees exactly TWO edges of each color, so the coloring is balanced: (n-1)/m=2. This is a small balanced coloring, not proof of existence/absence of rainbow H for arbitrarily large n.
This finite fixture tests the conventions. It does not certify any of the asymptotic or all-graphs assertions.
What is known
Maintained #811 remains OPEN as a classification question, but the Clemen–Wagner primary published abstract directly proves the K4 counterexample and Clemen–Wagner, Balanced Edge-Colorings Avoiding Rainbow Cliques of Size Four, Electronic J Combinatorics 30(3) (2023) P3.17 directly published abstract shows balanced 6-colorings of K_(13^k) without a rainbow K4 for each k. Axenovich–Clemen, Rainbow subgraphs in edge-colored complete graphs: Answering two questions by Erdős and Tuza, J Graph Theory 106 (2024) 57–66 DOI 10.1002/jgt.23063, gives more clique families. Original journal abstract and full theorem 3.3 on Wiley page checked. Their constructions DO NOT classify all H or settle C6, and should not convert OPEN to wholly DISPROVED.
The distinctions between established partial theorems, original open parts, and disproved universal claims have been preserved. Historical publications are attributed, rather than presented as new GCL mathematics.
If the target graph has \(m\) edges, a balanced \(m\) coloring of \(K_n\) requires
for every vertex \(v\) and each color \(i\). The 2023 paper constructs a balanced six-coloring of \(K_{13^k}\) with no rainbow \(K_4\), for all positive integers \(k\). This refutes the all-target assertion, not the open classification of all possible targets.
GCL's current state
The original authenticated source-return record has a disposition of STATUS_CONFLICT. This explanatory manuscript is editorially reviewed through protected EC-BULK-005-R4. The K4 counterexamples remain distinct from the open graph-classification question; STATUS_CONFLICT source provenance persists, and editorial acceptance does not certify theorem proofs. The mathematical status of individual subquestions is not determined by a single registry label.
What remains
Implement balanced-degree histogram for cyclic K7 with three distance colors, separately detect rainbow triangles. Source-lock precise 2023 K4 family K_(13^k), and 2024 theorem parameter ranges. Do not claim all-graph closure; preserve all H classification OPEN while universal yes is refuted.
An editorial source review can verify the published K4 counterexample from its primary abstract and reproduce the cyclic K7 balanced fixture; the full classification and the C6 question remain unproved here.
Sources and claim boundaries
- Erdos problem #811 and maintained source and bibliography, retrieved by web search 14 October 2026.
- Authenticated issue-bound return for #811, preserving source limitations and open proof obligations.
- Pinned teorth/erdosproblems repository revision 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml, source blob 4e60263a80af6207aca494d2e1388e44fa372889. No protected source lock was silently changed.
- M. Axenovich and F. C. Clemen, Rainbow subgraphs in edge-colored complete graphs, Journal of Graph Theory 106 (2024), 57-66, DOI https://doi.org/10.1002/jgt.23063. F. C. Clemen and A. Z. Wagner, Balanced Edge-Colorings Avoiding Rainbow Cliques of Size Four, Electronic Journal of Combinatorics 30(3) (2023), P3.17, DOI https://doi.org/10.37236/11965.
- Editorial acceptance: Protected V2 batch EC-BULK-005-R4, exact-hash bound. Source publication: protected merge completed. Public mathematical rendering: verified before admission. New theorem certification: NONE.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2082 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: STATEMENT_CAPTURE_REQUIRED.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.