Non-three-colourable common graphs exist
Hatami, Hamed, Hladký, Jan, Kral', Daniel, Norine, Serguei and Razborov, Alexander. (2012) Non-three-colourable common graphs exist. Combinatorics, Probability and Computing, Vol.21 (No.5). pp. 734-742. ISSN 0963-5483Full text not available from this repository.
Official URL: http://dx.doi.org/10.1017/S0963548312000107
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 Erdős, 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, Št'ovíček 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.
|Item Type:||Journal Article|
|Divisions:||Faculty of Science > Mathematics|
|Journal or Publication Title:||Combinatorics, Probability and Computing|
|Publisher:||Cambridge University Press|
|Page Range:||pp. 734-742|
Actions (login required)
Downloads per month over past year