Advances on defective parameters in graphs
|Title||Advances on defective parameters in graphs|
|Publication Type||Journal Article|
|Year of Publication||2015|
|Authors||Akdemir, A., and T. Ekim|
|Keywords||Cocritical graphs, Defective cocoloring, Defective Ramsey numbers, 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 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.