کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4657269 | 1343727 | 2008 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The Erdős–Hajnal conjecture for bull-free graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 98, Issue 6, November 2008, Pages 1301-1310
Journal: Journal of Combinatorial Theory, Series B - Volume 98, Issue 6, November 2008, Pages 1301-1310