Advances on defective parameters in graphs

• kk-sparse and kk-dense sets generalize respectively independent sets and cliques.
• Defective Ramsey numbers avoiding kk-sparse and kk-dense sets are studied.
• Lower and upper bounds for unknown defective Ramsey Numbers are computed.
• The problem of partitioning graphs into kk-sparse or kk-dense sets is studied.
• Efficient graph generation methods are used to compute some defective parameters.

We consider the generalization of Ramsey numbers to the defective framework using kk-dense and kk-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 kk-sparse and kk-dense sets. By the help of efficient graph generation methods, we show that c0(4)=12,c1(3)=12c0(4)=12,c1(3)=12 and c2(2)=10c2(2)=10 where ck(m)ck(m) is the maximum order nn such that all nn-graphs can be kk-defectively cocolored using at most mm colors. We also give the numbers of kk-defective mm-cocritical graphs of order nn (until n=10n=10) for different levels of defectiveness and m=2,3m=2,3 and 4.