Small 1-defective Ramsey numbers in perfect graphs

TitleSmall 1-defective Ramsey numbers in perfect graphs
Publication TypeJournal Article
Year of Publication2019
AuthorsEkim, T., J. Gimbel, and O. Şeker
JournalDiscrete Optimization
Keywords-dense, -dependent, -sparse, Extremal graphs

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.