Publication details
Non-Three-Colourable Common Graphs Exist
| Authors | |
|---|---|
| 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. |