Small 1-defective Ramsey numbers in perfect graphs
Title | Small 1-defective Ramsey numbers in perfect graphs |
Publication Type | Journal Article |
Year of Publication | 2019 |
Authors | Ekim, T., J. Gimbel, and O. Şeker |
Journal | Discrete Optimization |
Volume | 34 |
Pagination | 100548 |
ISSN | 1572-5286 |
Keywords | -dense, -dependent, -sparse, Extremal graphs |
Abstract | 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 R1PG(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 R1PG(3,j)=j for any j≥2, R1PG(4,4)=6, R1PG(4,5)=8, R1PG(4,6)=10, R1PG(4,7)=13, R1PG(4,8)=15 and R1PG(5,5)=13. We exhibit all extremal graphs for R1PG(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. |
URL | https://www.sciencedirect.com/science/article/pii/S1572528618301622 |
DOI | 10.1016/j.disopt.2019.06.001 |