Small 1-defective Ramsey numbers in perfect graphs
| Autor: | Oylum Şeker, Tınaz Ekim, John Gimbel |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Combinatorics
021103 operations research Computational Theory and Mathematics 010201 computation theory & mathematics Applied Mathematics 0211 other engineering and technologies Order (group theory) 0102 computer and information sciences 02 engineering and technology Ramsey's theorem 01 natural sciences Theoretical Computer Science Mathematics |
| Zdroj: | Discrete Optimization. 34:100548 |
| ISSN: | 1572-5286 |
| DOI: | 10.1016/j.disopt.2019.06.001 |
| Popis: | 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 R 1 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 R 1 PG ( 3 , j ) = j for any j ≥ 2 , R 1 PG ( 4 , 4 ) = 6 , R 1 PG ( 4 , 5 ) = 8 , R 1 PG ( 4 , 6 ) = 10 , R 1 PG ( 4 , 7 ) = 13 , R 1 PG ( 4 , 8 ) = 15 and R 1 PG ( 5 , 5 ) = 13 . We exhibit all extremal graphs for R 1 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 R 1 Δ PG ( 4 , 7 ) = 12 . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect