Problem 811

Suppose $n\equiv 1\pmod{m}$ . We say that an edge-colouring of $K_n$ using $m$ colours is balanced if every vertex sees exactly $\lfloor n/m\rfloor$ many edges of each colours.

For which graphs $G$ is it true that, if $m=e(G)$ , for all large $n\equiv 1\pmod{m}$ , every balanced edge-colouring of $K_n$ with $m$ colours contains a rainbow copy of $G$ ? (That is, a subgraph isomorphic to $G$ where each edge receives a different colour.)

Source: erdosproblems.com/811

Graph theory
Ramsey theory

Wiki page

Status

Open

No claim settles this problem.

Open: the site labels the problem OPEN (last edited 14 October 2025), and the classification is not known. Excluded from the answer set by refereed sources: Axenovich and Clemen 2022 (J. Graph Theory 106 (2024)) exclude every clique $K_q$ with $q\ge10$ and $q\equiv2,3\pmod4$ (their Theorem 1.4), every graph with an odd number $\ell$ of edges containing a clique on $\lfloor\sqrt\ell+7/2\rfloor$ vertices (their Theorem 3.3) and all but $(1+o(1))N/\log N$ of the clique sizes $q\le N$ (their Theorem 1.2, through their Lemma 4.1: no perfect difference set of size $q$ in $\mathbb Z_{q^2-q+1}$ excludes $K_q$ ), and Clemen and Wagner 2023 (Electron. J. Combin. 30 (2023), Theorem 1.2) exclude $K_4$ . Two further exclusions are inferences taken on this page: $K_7$ , since a perfect difference set of size $7$ would be a projective plane of order $6$ , which does not exist (Lemma 4.1 with the Bruck--Ryser theorem), and every $K_q$ with $q\le2\cdot10^9$ and $q-1$ not a prime power (Lemma 4.1 with the computational verification of the prime power conjecture that the paper cites and this corpus has not read). The case $K_6$ is announced without proof, so of the cliques on at most twelve vertices $K_5$ , $K_6$ , $K_8$ , $K_9$ and $K_{12}$ are not excluded in the sources found, and Conjecture 1.3 of Axenovich and Clemen predicts every $K_q$ with $q\ge4$ . On the other side Erdős and Tuza 1993 place the forests, $K_3$ and $C_4$ in the answer set: their Theorem 2 (p. 82) gives $d(n,K_3)=2\lfloor(n-2)/8\rfloor+1$ exactly, their Theorem 3 (p. 83) gives $\lfloor n/6\rfloor\le d(n,C_4)\le(1/4-c)n$ for the quantitative version, and their Proposition 1 (p. 83) gives $d(n,F)\le2e-2$ for a forest with $e$ edges ( $e-1$ for a tree), below $(n-1)/e$ for large $n$ ; the paper's own summary (p. 81) names only the trees, $K_3$ and $C_4$ , "the only graphs for which we can prove that they satisfy the requirements of Problems 1 and 2". The cycle $C_6$ that Erdős singled out is open in the sources found. A forum comment of 15 September 2026 claims a Lean-verified proof of Conjecture 1.3, recorded as the unreviewed partial claim Kitamura 2026, which would exclude every clique on at least four vertices and leave the classification open. The search, whose scope the Current assessment records, found nothing else. This is a bounded negative finding, not a certificate of openness.

AxCl24: Axenovich, M. and Clemen, F. C., Rainbow subgraphs in edge-colored complete graphs: answering two questions by Erdős and Tuza. J. Graph Theory 106 (2024), no. 1, 57--66, doi:10.1002/jgt.23063 (published online 12 December 2023). Page numbers are those of arXiv:2209.13867v2 (28 November 2022): Theorems 1.2, 1.4, 1.6 and Conjecture 1.3, p. 2; Theorem 3.3, p. 5; Lemma 4.1 and Corollary 4.3, pp. 6--7. Library home: Axenovich and Clemen 2024.
ClWa23: Clemen, F. C. and Wagner, A. Z., Balanced edge-colorings avoiding rainbow cliques of size four. Electron. J. Combin. 30 (2023), no. 3, Paper No. 3.17, doi:10.37236/11965 (published 11 August 2023); page numbers are those of arXiv:2303.15476v1 (26 March 2023), titled there "A note on balanced edge-colorings avoiding rainbow cliques of size four". Theorem 1.2, p. 1. Library home: Clemen and Wagner 2023.
ErTu93: Erdős, P. and Tuza, Z., Rainbow subgraphs in edge-colorings of complete graphs. Quo vadis, graph theory?, Ann. Discrete Math. 55, North-Holland (1993), 81--88, doi:10.1016/S0167-5060(08)70377-7. The origin of the question (its Problem 1, p. 81) and the site's source for the $d_{C_4}(n)$ bounds. The printed chapter (eight pages): the definitions, Problems 1--2 and the candidates paragraph, p. 81; Problems 3--5 and Theorem 2, p. 82; Theorem 3, Proposition 1, Theorem 4 and Theorem 5, p. 83. Library home: Erdős and Tuza 1993; result pages Erdős and Tuza 1993, Problem 1 (p. 81 = PDF p. 1), Erdős and Tuza 1993, Theorem 2 (p. 82 = PDF p. 2) and Erdős and Tuza 1993, Theorem 3 (p. 83 = PDF p. 3).
Er91: Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988) (1991), 397--406 (as the site's reference text prints it). Not held: past the Rényi archive's 1989 cutoff, no attempt made.
Er93: Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350; the site cites p. 346. Chapter V, problem 11, printed p. 346: the Pyber--Tuza--Erdős conjecture for $K(12n+1)$ colored by six colors with every vertex of degree $2n$ in every color, asking for a totally multicolored $C_6$ and a totally multicolored $K_4$ . Library home: Erdős 1993.
Er96: Erdős, Paul, Some of my favourite problems on cycles and colourings. Tatra Mt. Math. Publ. 9 (1996), 7--9 (received 8 September 1994). [AxCl24] cites it as the restatement of the question and [ClWa23] for the remark singling out $C_6$ and $K_4$ . The journal archive's volume listing serves the paper as a dvips PostScript file (three pages). Item 6, printed p. 9: the balanced $e$ -coloring question and the $C_6$ and $K_4$ challenge. Library home: Erdős 1996.
Pe21: Peluse, S., An asymptotic version of the prime power conjecture for perfect difference sets. Math. Ann. 380 (2021), no. 3-4, 1387--1425. The input to Theorem 1.2 of [AxCl24]; not held.
Tu13: Tuza, Z., Problems on cycles and colorings. Discrete Math. 313 (2013), no. 19, 2007--2013. Repeats both Erdős--Tuza questions ([AxCl24], p. 2); not held.

Problem 811

Status

Proof claims

Discussion