Publication details

Non-Three-Colourable Common Graphs Exist

Authors

HATAMI H HLADKY J KRÁĽ Daniel NORINE S RAZBOROV A

Year of publication 2012
Type Article in Periodical
Magazine / Source COMBINATORICS PROBABILITY & COMPUTING
Citation
Doi http://dx.doi.org/10.1017/S0963548312000107
Description A graph H is called 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 minimized by taking G to be a random graph. Extending a conjecture of Erdos, Burr and Rosta conjectured that every graph is common. Thomason disproved both conjectures by showing that K-4 is not common. It is now known that in fact the common graphs are very rare. Answering a question of Sidorenko and of Jagger, St' ovicek 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-colourable.

You are running an old browser version. We recommend updating your browser to its latest version.

More info