Non-Three-Colourable Common Graphs Exist

被引：32

作者：

Hatami, Hamed ^{[1
]}

Hladky, Jan ^{[2
,3
]}

Kral, Daniel ^{[4
]}

Norine, Serguei ^{[5
]}

Razborov, Alexander ^{[6
]}

机构：

[1] McGill Univ, Sch Comp Sci, Montreal, PQ, Canada

[2] Charles Univ Prague, Fac Math & Phys, Dept Appl Math, Prague 11800, Czech Republic

[3] Univ Warwick, Dept Comp Sci, DIMAP, Coventry CV4 7AL, W Midlands, England

[4] Charles Univ Prague, Fac Math & Phys, Inst Theoret Comp Sci, Prague 11800, Czech Republic

[5] Princeton Univ, Dept Math, Princeton, NJ 08544 USA

[6] Univ Chicago, Dept Comp Sci, Chicago, IL 60637 USA

来源：

COMBINATORICS PROBABILITY & COMPUTING | 2012年 / 21卷 / 05期

基金：

加拿大自然科学与工程研究理事会; 欧洲研究理事会; 俄罗斯基础研究基金会; 英国工程与自然科学研究理事会;

关键词：

D O I：

10.1017/S0963548312000107

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：734 / 742

页数：9

共 20 条

[11] Hladky J., 2009, ARXIV09082791
[12] Multiplicities of subgraphs
Jagger, C
Stovicek, P
Thomason, A
[J]. COMBINATORICA, 1996, 16 (01) : 123 - 141
[13] Flag algebras
Razborov, Alexander A.
[J]. JOURNAL OF SYMBOLIC LOGIC, 2007, 72 (04) : 1239 - 1282
[14] ON 3-HYPERGRAPHS WITH FORBIDDEN 4-VERTEX CONFIGURATIONS
Razborov, Alexander A.
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (03) : 946 - 963
[15] Sidorenko A, 1996, RANDOM STRUCT ALGOR, V8, P229, DOI 10.1002/(SICI)1098-2418(199605)8:3<229::AID-RSA6>3.0.CO
[16] 2-#
[17] Sidorenko A, 1989, MAT ZAMETKI, V46, P104
[18] Sidorenko A F., 1989, Matematicheskie Zametki, V46, P72
[19] Sidorenko AF., 1991, DISKRET MAT, V3, P50
[20] THOMASON A, 1989, J LOND MATH SOC, V39, P246

← 1 2 →