The Erdos-Hajnal conjecture for bull-free graphs

被引：34

作者：

Chudnovsky, Maria ^{[1
]}

Safra, Shmuel ^{[2
]}

机构：

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

[2] Tel Aviv Univ, IL-69978 Tel Aviv, Israel

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2008年 / 98卷 / 06期

关键词：

Bull-free graphs; Induced subgraphs; Stable set; Clique;

D O I：

10.1016/j.jctb.2008.02.005

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The bull is a graph consisting, of a triangle and two pendant edges. A graphs is called bull-free if no induced subgraph of it is a bull. In this paper we prove that every bull-free graph on n vertices contains either a clique or a stable set of size n(1/4), thus settling the Erdos-Hajnal conjecture [P. Erdos, A. Hajnal, Ramsey-type theorems. Discrete Appl. Math. 25 (1989) 37-52] for the bull. (c) 2008 Elsevier Inc. All rights reserved.

引用

页码：1301 / 1310

页数：10

共 7 条

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

Alon, N ;

Pach, J ;

Solymosi, J .

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

[2]

CHUDNOVSKY M, STRUCTURE BULL UNPUB

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

Chudnovsky, Maria ;

Robertson, Neil ;

Seymour, Paul ;

Thomas, Robin .

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

[4]

Cook W., 1998, Combinatorial Optimization

[5] RAMSEY-TYPE THEOREMS [J].

ERDOS, P ;

HAJNAL, A .

DISCRETE APPLIED MATHEMATICS, 1989, 25 (1-2) :37-52

[6]

Gyarfas A., 1997, ALGORITHMS COMB, V14, P93

[7]

Lovasz L., 1972, DISCRETE MATH, V2, P253, DOI DOI 10.1016/0012-365X(72)90006-4

← 1 →