Advances on defective parameters in graphs

TitleAdvances on defective parameters in graphs
Publication TypeJournal Article
Year of Publication2015
AuthorsAkdemir, A., and T. Ekim
JournalDiscrete Optimization
KeywordsCocritical 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.