The Erdos-Hajnal Conjecture-A Survey

被引：58

作者：

Chudnovsky, Maria ^{[1
]}

机构：

[1] Columbia Univ, New York, NY 10027 USA

来源：

JOURNAL OF GRAPH THEORY | 2014年 / 75卷 / 02期

关键词：

induced subgraphs; Erdos-Hajnal conjecture; RAMSEY-TYPE THEOREMS; GRAPHS; SUBGRAPHS;

D O I：

10.1002/jgt.21730

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The Erdos-Hajnal conjecture states that for every graph H, there exists a constant (H)>0 such that every graph G with no induced subgraph isomorphic to H has either a clique or a stable set of size at least |V(G)|(H). This article is a survey of some of the known results on this conjecture. (c) 2013 Wiley Periodicals, Inc. J. Graph Theory 75: 178-190, 2014

引用

页码：178 / 190

页数：13

共 25 条

[1] Testing subgraphs in directed graphs
Alon, N
Shapira, A
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2004, 69 (03) : 354 - 382
[2] Ramsey-type theorems with forbidden subgraphs
Alon, N
Pach, J
Solymosi, J
[J]. COMBINATORICA, 2001, 21 (02) : 155 - 170
[3] Berger E., FORCING LARGE TRANSI
[4] Tournaments and colouring
Berger, Eli
Choromanski, Krzysztof
Chudnovsky, Maria
Fox, Jacob
Loebl, Martin
Scott, Alex
Seymour, Paul
Thomasse, Stephan
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2013, 103 (01) : 1 - 20
[5] Choromanski K., TOURNAMENTS NEAR LIN
[6] Upper Bounds for Erdos-Hajnal Coefficients of Tournaments
Choromanski, Krzysztof
[J]. JOURNAL OF GRAPH THEORY, 2013, 74 (01) : 122 - 132
[7] Chudnovsky M., EXTENDING GYARFAS SU
[8] The Erdos-Hajnal conjecture for bull-free graphs
Chudnovsky, Maria
Safra, Shmuel
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2008, 98 (06) : 1301 - 1310
[9] Large cliques or stable sets in graphs with no four-edge path and no five-edge path in the complement
Chudnovsky, Maria
Zwols, Yori
[J]. JOURNAL OF GRAPH THEORY, 2012, 70 (04) : 449 - 472
[10] The strong perfect graph theorem
Chudnovsky, Maria
Robertson, Neil
Seymour, Paul
Thomas, Robin
[J]. ANNALS OF MATHEMATICS, 2006, 164 (01) : 51 - 229

← 1 2 3 →