Small 1-defective Ramsey numbers in perfect graphs
Discrete Optimization, cilt.34, 2019 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 34
- Basım Tarihi: 2019
- Doi Numarası: 10.1016/j.disopt.2019.06.001
- Dergi Adı: Discrete Optimization
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Anahtar Kelimeler: Extremal graphs, k-dense, k-dependent, k-sparse
- Boğaziçi Üniversitesi Adresli: Evet
Özet
In this paper, we initiate the study of defective Ramsey numbers for the class of perfect graphs. Let PG be the class of all perfect graphs and R1 PG(i,j) denote the smallest n such that all perfect graphs on n vertices have either a 1-dense i-set or a 1-sparse j-set. We show that R1 PG(3,j)=j for any j≥2, R1 PG(4,4)=6, R1 PG(4,5)=8, R1 PG(4,6)=10, R1 PG(4,7)=13, R1 PG(4,8)=15 and R1 PG(5,5)=13. We exhibit all extremal graphs for R1 PG(4,7)=13 (there are exactly three). We also obtain the 1-defective Ramsey number of order (4,7) in triangle-free perfect graphs, namely R1 ΔPG(4,7)=12.