---

Claim. M. Axenovich and F. C. Clemen, Rainbow subgraphs in edge-colored complete graphs: answering two questions by Erdős and Tuza, J. Graph Theory 106 (2024), no. 1, 57--66 (arXiv:2209.13867; page numbers below are those of v2). For a graph $F$ with $\ell$ edges they write $d(n,F)=\infty$ when $K_n$ has an $(\ell,\lfloor(n-1)/\ell\rfloor)$-coloring without a rainbow $F$; for $\ell\mid n-1$ this is a balanced coloring in the sense of Problem 811. The paper proves three exclusions.

• Theorem 3.3 (p. 5): "Let $\ell\geq 3$ be an odd integer. For every integer $k\geq 1$ and $n=(\ell+1)^k$ there is a completely balanced coloring of $K_n$ with $\ell$ colors without a rainbow $K_m$, where $m=\left\lfloor\sqrt{\ell}+\frac{7}{2}\right\rfloor$."
• Theorem 1.4 (p. 2), which follows from Theorem 3.3: for $q\ge10$ with $q\equiv2$ or $3\pmod4$ and $\ell=\binom q2$, every $n=(\ell+1)^k$ carries a completely balanced $\ell$-coloring of $K_n$ with no rainbow $K_q$.
• Theorem 1.2 (p. 2): the set $S(N)$ of $q\in[4,N]$ with $d(n,K_q)=\infty$ for infinitely many admissible $n$ has size $N-(1+o(1))N/\log N$, proved from their Lemma 4.1 (no perfect difference set of size $q$ in $\mathbb Z_{q^2-q+1}$ gives such colorings) and Peluse's count of the $q$ that have a perfect difference set, which the paper cites.

Covers. Outside the answer set: every clique $K_q$ with $q\ge10$ and $q\equiv2,3\pmod4$ (Theorem 1.4, since $(\ell+1)^k\equiv1\pmod\ell$); every graph with an odd number $\ell$ of edges that contains $K_{\lfloor\sqrt\ell+7/2\rfloor}$ (Theorem 3.3); and all but $(1+o(1))N/\log N$ of the clique sizes $q\le N$ (Theorem 1.2). It does not cover the cases $q=6,7$, which the remark after Theorem 1.4 announces without proof, and Theorem 1.6, which concerns colorings with $\ell+1$ colors, answers the Erdős--Tuza variant and not this problem. The paper's Conjecture 1.3, that every $K_q$ with $q\ge4$ is excluded, is not part of the claim.

Depends on. Nothing in this wiki; the results are the paper's own theorems, with Theorem 1.2 resting on Peluse's cited theorem.

Acceptance. Refereed: Journal of Graph Theory, volume 106 (2024), no. 1, 57--66. The site's commentary credits the paper with infinitely many graphs lacking the property, but the site labels the problem OPEN, so no reviewed evidence is listed.