Problem 810

Does there exist some $\epsilon>0$ such that, for all sufficiently large $n$ , there exists a graph $G$ on $n$ vertices with at least $\epsilon n^2$ many edges such that the edges can be coloured with $n$ colours so that every $C_4$ receives $4$ distinct colours?

Source: erdosproblems.com/810

Graph theory
Ramsey theory

Wiki page

Status

Open

No claim settles this problem.

Open: the site labels the problem OPEN (last edited 1 April 2026), and no source found in the search proves or refutes the statement. The 1989 paper states without proof that $n$ colors suffice for $C_4$ at $e=c\,g(n;7,4)$ edges, which reaches $\epsilon n^2$ only if $g(n;7,4)$ has order $n^2$ , itself an open question (the site's Problem 1178); its second bound, $n$ colors at $e=c\,r_4(n)$ edges, is trivially true as printed, since $r_4(n)=o(n)$ by Szemerédi's theorem and a graph with at most $n$ edges can give every edge its own color, and is probably a misprint for $e=c\,n\,r_4(n)$ , on the model of the paper's $P_4$ bound (6.3), a bound that is unproved and still $o(n^2)$ ; Sárközy and Selkow proved in 2006 that for every connected bipartite $L$ that is not complete bipartite and every $\alpha,c>0$ , $\chi_S(n,e,L)>cn$ once $e>\alpha n^2$ and $n$ is large in terms of $\alpha$ , $c$ and $L$ , and wrote that the question "still remains open for complete bipartite graphs that are not stars, for instance for $C_4$ ". The search, whose scope the Current assessment records, found nothing later on $C_4$ . This is a bounded negative finding, not a certificate of openness.

BEGS89: Burr, S. A., Erdős, P., Graham, R. L. and Sós, V. T., Maximal antiramsey graphs and the strong chromatic number. J. Graph Theory 13 (1989), no. 3, 263--282, doi:10.1002/jgt.3190130302. Theorems 6.1--6.2, p. 271; Theorem 6.3, p. 272; the $C_4$ passage, p. 273; the Rényi archive's scan of the paper is public. The site's key "BEGS8" is this paper. Library home: Burr 1989.
SaSe06: Sárközy, G. N. and Selkow, S., On an anti-Ramsey problem of Burr, Erdős, Graham, and T. Sós. J. Graph Theory 52 (2006), no. 2, 147--156, doi:10.1002/jgt.20148 (published online 25 January 2006). Theorem 4, p. 3 of the authors' preprint of 5 February 2004. Library home: Sárközy and Selkow 2006.
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); the site cites p. 399. Not held: the paper is past the Rényi archive's 1989 cutoff.
RuSz78: Ruzsa, I. Z. and Szemerédi, E., Triple systems with no six points carrying three triangles. Combinatorics II, North-Holland, Amsterdam (1978), 939--945 (as the 1989 paper's reference list prints it); its [10], behind Theorem 6.3 and the remark that gives the $r_4(n)$ bound. Not held.
BEFGS: Burr, S. A., Erdős, P., Frankl, P., Graham, R. L. and Sós, V. T., "to appear": the 1989 paper's [4], carrying the proofs of its Theorems 6.1--6.2. Bucić, Chen and Ma cite a chapter "Further results on maximal antiramsey graphs" by these authors in Graph Theory, Combinatorics and Applications, Vol. I, Wiley (1988), 193--206 (their reference [5]), which may be that paper; not held, and the identification is unverified.

Problem 810

Status

Proof claims

Discussion