Chromatic Number of Common Graphs
Status solved high confidence
The question is resolved negatively: common graphs do not have bounded chromatic number. Kráľ, Volec, and Wei proved that for every positive integer $k$ there exists a connected common graph with chromatic number $k$, answering the question posed in [HHKNR] as well as a problem from the Conlon–Fox–Sudakov survey. Ko and Lee subsequently strengthened this by showing that for any $k, r > 0$ there exists a $k$-connected common graph with chromatic number at least $r$.
Cited literature (2)
-
Constructs a connected common graph with chromatic number $k$ for every positive integer $k$, proving that common graphs can have arbitrarily large chromatic number and resolving the question of Hatami–Hladký–Kráľ–Norine–Razborov.
-
Strengthens the Kráľ–Volec–Wei result by showing that for any $k, r > 0$ there exists a $k$-connected common graph with chromatic number at least $r$, answering a further question of Kráľ, Volec, and Wei.
Reviewer notes. The Kráľ–Volec–Wei paper (arXiv June 2022) was published in Compositio Mathematica Vol. 161, No. 3, pp. 594–634 (published online July 3, 2025; in print March 2025). The Ko–Lee paper (arXiv July 2022) was published in J. Combin. Theory Ser. B 162 (2023), pp. 223–230, DOI 10.1016/j.jctb.2023.06.001. The Ko–Lee contribution is classified 'partial' in the sense that it strengthens rather than independently resolves the original question.
Discussion
A graph $ H $ is common if the sum of the number of copies of $ H $ in a graph $ G $ and the number in the complement of $ G $ is asymptotically minimised by taking $ G $ to be a random graph (see [HHKNR] for a formal definition). Goodman proved that $ K_3 $ is common [G]. Erdös [E] conjectured that every complete graph is common. Later, this conjecture was extended to all graphs by Burr and Rosta [BR]. Sidorenko [S89] disproved Burr and Rosta’s conjecture by showing that a triangle with a pendant edge is not common. Conjectures of Erdös and Simonovits [ES] and Sidorenko [S91,S93] imply that every bipartite graph is common. Disproving the first conjecture of Erdös, Thomason proved that $ K_4 $ is not common [T]. More generally, Jagger, Šťovíček and Thomason proved that no common graph contains $ K_4 $ as a subgraph [JST]. The 5-wheel is an example of a 4-chromatic common graph [HHKNR].
Bibliography
-
[BR]Burr, S. A. and Rosta, V. On the Ramsey multiplicities of graphs: Problems and recent results. J. Graph Theory 4 (1980) 347–361. -
[E]Paul Erdös, On the number of complete subgraphs contained in certain graphs. Magyar Tud. Akad. Mat. Kutato ́ Int. Ko ̈zl. 7 (1962) 459–464. -
[ES]Paul Erdös and Miklós Simonovits (1984) Cube-supersaturated graphs and related problems. In Progress in Graph Theory: Waterloo, Ont., 1982, Academic Press, pp. 203–218. -
★
[HHKNR]H. Hatami, J. Hladký, D. Kráľ, S. Norine, A. Razborov: Non-three-colorable common graphs exist, Combinatorics, Probability and Computing 21 (2012), 734–742. -
[JST]Jagger, Chris; Šťovíček, Pavel; Thomason, Andrew. Multiplicities of subgraphs. Combinatorica 16 (1996) 123–141. -
[S89]Sidorenko, A. Cycles in graphs and functional inequalities. Mat. Zametki 46 (1989) 72–79, 104. -
[S91]Sidorenko, A. Inequalities for functionals generated by bipartite graphs. Diskret. Mat. 3 (1991) 50–65. -
[S93]Sidorenko, A. A correlation inequality for bipartite graphs. Graphs Combin. 9 (1993) 201–204. -
[T]Thomason, Andrew. A disproof of a conjecture of Erdo ̋s in Ramsey theory, J. London Math. Soc. (2) 39 (1989) 246–255.