The Library
Non-three-colourable common graphs exist
Tools
Tools
Tools
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-5483
Full text not available from this repository.
Official URL: http://dx.doi.org/10.1017/S0963548312000107
Abstract
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 |
| ISSN: | 0963-5483 |
| Date: | 2012 |
| Volume: | Vol.21 |
| Number: | No.5 |
| Page Range: | pp. 734-742 |
| Identification Number: | 10.1017/S0963548312000107 |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| URI: | http://wrap.warwick.ac.uk/id/eprint/49074 |
Actions (login required)
 |
View Item |
