| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4657269 | Journal of Combinatorial Theory, Series B | 2008 | 10 Pages |
Abstract
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 , thus settling the Erdős–Hajnal conjecture [P. Erdős, A. Hajnal, Ramsey-type theorems, Discrete Appl. Math. 25 (1989) 37–52] for the bull.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
