Defective Ramsey Numbers and Defective Cocolorings in Some Subclasses of Perfect Graphs
Graphs and Combinatorics, cilt.39, sa.1, 2023 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 39 Sayı: 1
- Basım Tarihi: 2023
- Doi Numarası: 10.1007/s00373-023-02612-4
- Dergi Adı: Graphs and Combinatorics
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, MathSciNet, zbMATH, Civil Engineering Abstracts
- Anahtar Kelimeler: Bipartite graphs, Chordal graphs, Cographs, Efficient graph generation, Perfect graphs
- Boğaziçi Üniversitesi Adresli: Evet
Özet
In this paper, we investigate a variant of Ramsey numbers called defective Ramsey numbers where cliques and independent sets are generalized to k-dense and k-sparse sets, both commonly called k-defective sets. We focus on the computation of defective Ramsey numbers restricted to some subclasses of perfect graphs. Since direct proof techniques are often insufficient for obtaining new values of defective Ramsey numbers, we provide a generic algorithm to compute defective Ramsey numbers in a given target graph class. We combine direct proof techniques with our efficient graph generation algorithm to compute several new defective Ramsey numbers in perfect graphs, bipartite graphs and chordal graphs. We also initiate the study of a related parameter, denoted by ckG(m), which is the maximum order n such that the vertex set of any graph of order n in a class G can be partitioned into at most m subsets each of which is k-defective. We obtain several values for ckG(m) in perfect graphs and cographs.