Advances on defective parameters in graphs

作者：Akdemir Ahu; Ekim Tinaz^*

来源：Discrete Optimization, 2015, 16: 62-69.

DOI：10.1016/j.disopt.2015.01.002

• Defective Ramsey numbers
• Defective cocoloring
• Cocritical graphs
• Efficient graph generation

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 c(0)(4) = 12, c(1)(3) = 12 and c(2)(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.

• 出版日期2015-5