The Library
Non-three-colourable common graphs exist
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. doi:10.1017/S0963548312000107 ISSN 0963-5483.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Combinatorics, Probability and Computing | ||||
Publisher: | Cambridge University Press | ||||
ISSN: | 0963-5483 | ||||
Official Date: | 2012 | ||||
Dates: |
|
||||
Volume: | Vol.21 | ||||
Number: | No.5 | ||||
Page Range: | pp. 734-742 | ||||
DOI: | 10.1017/S0963548312000107 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |