Advances on defective parameters in graphs
Discrete Optimization, cilt.16, ss.62-69, 2015 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 16
- Basım Tarihi: 2015
- Doi Numarası: 10.1016/j.disopt.2015.01.002
- Dergi Adı: Discrete Optimization
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.62-69
- Anahtar Kelimeler: Cocritical graphs, Defective cocoloring, Defective Ramsey numbers, Efficient graph generation
- Boğaziçi Üniversitesi Adresli: Evet
Özet
We consider the generalization of Ramsey numbers to the defective framework using k-dense and k-sparse sets. We construct the first tableaux for defective Ramsey numbers with exact values whenever it is known, and lower and upper bounds otherwise. In light of defective Ramsey numbers, we consider the defective cocoloring problem which consists of partitioning the vertex set of a given graph into k-sparse and k-dense sets. By the help of efficient graph generation methods, we show that c0(4)=12,c1(3)=12 and c2(2)=10 where ck(m) is the maximum order n such that all n-graphs can be k-defectively cocolored using at most m colors. We also give the numbers of k-defective m-cocritical graphs of order n (until n=10) for different levels of defectiveness and m=2,3 and 4.