{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T18:54:09Z","timestamp":1780599249428,"version":"3.54.1"},"reference-count":20,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2012,3,16]],"date-time":"2012-03-16T00:00:00Z","timestamp":1331856000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2012,9]]},"abstract":"<jats:p>A graph <jats:italic>H<\/jats:italic> is called <jats:italic>common<\/jats:italic> if the sum of the number of copies of <jats:italic>H<\/jats:italic> in a graph <jats:italic>G<\/jats:italic> and the number in the complement of <jats:italic>G<\/jats:italic> is asymptotically minimized by taking <jats:italic>G<\/jats:italic> to be a random graph. Extending a conjecture of Erd\u0151s, Burr and Rosta conjectured that every graph is common. Thomason disproved both conjectures by showing that <jats:italic>K<\/jats:italic><jats:sub>4<\/jats:sub> is not common. It is now known that in fact the common graphs are very rare. Answering a question of Sidorenko and of Jagger, \u0160t'ov\u00ed\u010dek 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.<\/jats:p>","DOI":"10.1017\/s0963548312000107","type":"journal-article","created":{"date-parts":[[2012,3,16]],"date-time":"2012-03-16T10:36:49Z","timestamp":1331894209000},"page":"734-742","source":"Crossref","is-referenced-by-count":38,"title":["Non-Three-Colourable Common Graphs Exist"],"prefix":"10.1017","volume":"21","author":[{"given":"HAMED","family":"HATAMI","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"JAN","family":"HLADK\u00dd","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"DANIEL","family":"KR\u00c1L'","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"SERGUEI","family":"NORINE","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"ALEXANDER","family":"RAZBOROV","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2012,3,16]]},"reference":[{"key":"S0963548312000107_ref15","doi-asserted-by":"publisher","DOI":"10.1137\/090747476"},{"key":"S0963548312000107_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190040403"},{"key":"S0963548312000107_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02125347"},{"key":"S0963548312000107_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-010-0005-1"},{"key":"S0963548312000107_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-010-0097-0"},{"key":"S0963548312000107_ref12","doi-asserted-by":"crossref","unstructured":"[12] Hladk\u00fd J. , Kr\u00e1l' D. and Norine S. (2009) Counting flags in triangle-free digraphs. arXiv:0908.2791.","DOI":"10.1016\/j.endm.2009.07.105"},{"key":"S0963548312000107_ref1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548310000222"},{"key":"S0963548312000107_ref8","doi-asserted-by":"publisher","DOI":"10.2307\/2310464"},{"key":"S0963548312000107_ref5","doi-asserted-by":"publisher","DOI":"10.4310\/JOC.2011.v2.n1.a1"},{"key":"S0963548312000107_ref6","first-page":"459","article-title":"On the number of complete subgraphs contained in certain graphs","volume":"7","author":"Erd\u0151s","year":"1962","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl."},{"key":"S0963548312000107_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01300130"},{"key":"S0963548312000107_ref17","first-page":"50","article-title":"Inequalities for functionals generated by bipartite graphs","volume":"3","author":"Sidorenko","year":"1991","journal-title":"Diskret. Mat."},{"key":"S0963548312000107_ref20","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-39.2.246"},{"key":"S0963548312000107_ref14","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1203350785"},{"key":"S0963548312000107_ref11","unstructured":"[11] Hatami H. , Hladk\u00fd J. , Kr\u00e1l' D. , Norine S. and Razborov A. (2011) On the number of pentagons in triangle-free graphs. arXiv:1102.1634."},{"key":"S0963548312000107_ref16","first-page":"72","article-title":"Cycles in graphs and functional inequalities","volume":"46","author":"Sidorenko","year":"1989","journal-title":"Mat. Zametki"},{"key":"S0963548312000107_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/BF02988307"},{"key":"S0963548312000107_ref7","first-page":"203","volume-title":"Progress in Graph Theory: Waterloo, Ont., 1982","author":"Erd\u0151s","year":"1984"},{"key":"S0963548312000107_ref9","unstructured":"[9] Grzesik A. (2011) On the maximum number of C 5's in a triangle-free graph. arXiv:1102.0962."},{"key":"S0963548312000107_ref19","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199605)8:3<229::AID-RSA6>3.0.CO;2-#"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548312000107","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T23:02:25Z","timestamp":1556146945000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548312000107\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3,16]]},"references-count":20,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2012,9]]}},"alternative-id":["S0963548312000107"],"URL":"https:\/\/doi.org\/10.1017\/s0963548312000107","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3,16]]}}}