The Erdos-Hajnal conjecture for bull-free graphs

被引：33

作者：

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
Alon, N
Pach, J
Solymosi, J
[J]. COMBINATORICA, 2001, 21 (02) : 155 - 170
[2] CHUDNOVSKY M, STRUCTURE BULL UNPUB
[3] The strong perfect graph theorem
Chudnovsky, Maria
Robertson, Neil
Seymour, Paul
Thomas, Robin
[J]. ANNALS OF MATHEMATICS, 2006, 164 (01) : 51 - 229
[4] Cook W., 1998, Combinatorial Optimization
[5] RAMSEY-TYPE THEOREMS
ERDOS, P
HAJNAL, A
[J]. 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 →