Common graphs with arbitrary chromatic number

Ramsey’s theorem guarantees for every graph H that any 2-edge-coloring of a sufficiently large complete graph contains a monochromatic copy of H . In 1962, Erdős conjectured that the random 2-edge-coloring minimizes the number of monochromatic copies of Kₖ , and the conjecture was extended by Burr and Rosta to all graphs. In the late 1980s, the conjectures were disproved by Thomason and Sidorenko, respectively. A classification of graphs whose number of monochromatic copies is minimized by the random 2-edge-coloring, which are referred to as common graphs, remains a challenging open problem. If Sidorenko’s conjecture, one of the most significant open problems in extremal graph theory, is true, then every 2-chromatic graph is common and, in fact, no 2-chromatic common graph unsettled for Sidorenko’s conjecture is known. While examples of 3-chromatic common graphs were known for a long time, the existence of a 4-chromatic common graph was open until 2012, and no common graph with a larger chromatic number is known. We construct connected k -chromatic common graphs for every k . This answers a question posed by Hatami et al. [ Non-three-colourable common graphs exist , Combin. Probab. Comput. 21 (2012), 734–742], and a problem listed by Conlon et al. [ Recent developments in graph Ramsey theory , in Surveys in combinatorics 2015 , London Mathematical Society Lecture Note Series, vol. 424 (Cambridge University Press, Cambridge, 2015), 49–118, Problem 2.28]. This also answers in a stronger form the question raised by Jagger et al. [ Multiplicities of subgraphs , Combinatorica 16 (1996), 123–131] whether there exists a common graph with chromatic number at least four.