The Erdos-Hajnal Conjecture-A Survey

被引：62

作者：

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 [J].

Alon, N ;

Shapira, A .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2004, 69 (03) :354-382

[2] Ramsey-type theorems with forbidden subgraphs [J].

Alon, N ;

Pach, J ;

Solymosi, J .

COMBINATORICA, 2001, 21 (02) :155-170

[3]

Berger E., FORCING LARGE TRANSI

[4] Tournaments and colouring [J].

Berger, Eli ;

Choromanski, Krzysztof ;

Chudnovsky, Maria ;

Fox, Jacob ;

Loebl, Martin ;

Scott, Alex ;

Seymour, Paul ;

Thomasse, Stephan .

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 [J].

Choromanski, Krzysztof .

JOURNAL OF GRAPH THEORY, 2013, 74 (01) :122-132

[7]

Chudnovsky M., EXTENDING GYARFAS SU

[8] The Erdos-Hajnal conjecture for bull-free graphs [J].

Chudnovsky, Maria ;

Safra, Shmuel .

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 [J].

Chudnovsky, Maria ;

Zwols, Yori .

JOURNAL OF GRAPH THEORY, 2012, 70 (04) :449-472

[10] The strong perfect graph theorem [J].

Chudnovsky, Maria ;

Robertson, Neil ;

Seymour, Paul ;

Thomas, Robin .

ANNALS OF MATHEMATICS, 2006, 164 (01) :51-229