Non-three-colorable common graphs exist
arXiv:1105.0307 · doi:10.1017/S0963548312000107
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.
arXiv comment9 pages
References in corpus (2)
Cited by in corpus (17)
- Minimum number of monotone subsequences of length 4 in permutations
- Counting flags in triangle-free digraphs
- Crossing numbers of complete tripartite and balanced complete multipartite graphs
- Infinite dimensional finitely forcible graphon
- Elusive extremal graphs
- Non-bipartite k-common graphs
- The Inducibility of Graphs on Four Vertices
- Decomposing graphs into edges and triangles
- On the algebraic and topological structure of the set of Turán densities
- More about sparse halves in triangle-free graphs
- Finitely forcible graphons with an almost arbitrary structure
- Finitely forcible graph limits are universal
- Ramsey multiplicity and the Turán coloring
- Odd cycles in subgraphs of sparse pseudorandom graphs
- Common Pairs of Graphs
- Extremal problems and results related to Gallai-colorings
- The dimension of the feasible region of pattern densities