Non-three-colorable common graphs exist

Abstract

A graph H is called common if the total number of copies of H in every graph and its complement asymptotically minimizes for random graphs. A former conjecture of Burr and Rosta, extending a conjecture of Erdos asserted that every graph is common. Thomason disproved both conjectures by showing that the complete graph of order four is not common. It is now known that in fact the common graphs are very rare. Answering a question of Sidorenko and of Jagger, Stovicek and Thomason from 1996 we show that the 5-wheel is common. This provides the first example of a common graph that is not three-colorable.

9 pages

References in corpus (2)

• On the Number of Pentagons in Triangle-Free Graphs
• On the maximum number of five-cycles in a triangle-free graph

Cited by in corpus (16)

• Minimum number of monotone subsequences of length 4 in permutations
• Crossing numbers of complete tripartite and balanced complete multipartite graphs
• Infinite dimensional finitely forcible graphon
• Non-bipartite k-common graphs
• Elusive extremal graphs
• The Inducibility of Graphs on Four Vertices
• Decomposing graphs into edges and triangles
• More about sparse halves in triangle-free graphs
• On the algebraic and topological structure of the set of Turán densities
• Finitely forcible graph limits are universal
• Finitely forcible graphons with an almost arbitrary structure
• Ramsey multiplicity and the Turán coloring
• Common Pairs of Graphs
• The dimension of the feasible region of pattern densities
• Extremal problems and results related to Gallai-colorings
• Odd cycles in subgraphs of sparse pseudorandom graphs