Defective ramsey numbers and defective cocolorings

Abstract

Ramsey number, R(a; b), denotes the smallest positive integer n such that, among any n people, there exist a people who know each other or b people who do not know each other. R(a; b) values are known for small a and b values and for unknown R(a; b) values, the lower and upper bounds, namely the minimum and the maximum values that R(a; b) can take, has been calculated. In this study, we study a generalization of Ramsey numbers which is called defective Ramsey numbers. Defective Ramsey number, Rk(a; b), denotes the smallest positive integer n such that, among any n people, there exist a people who know each other or b people who do not know each other with at most k exceptions. We calculate some of the lower and upper bounds on some of the unknown Rk(a; b) values and improve some of the lower bounds. We also study classical and defective Ramsey numbers in some graph classes and derive some formulas that either give the exact value of or an upper bound on Ramsey numbers for a speci c graph class. In the second part, we study cocoloring of graphs. Cocoloring of a graph is an assignment of colors to the set of vertices such that each color class induces a clique or an independent set. We also studied defective cocoloring of graphs which considers k-denses, a defective clique in which the vertices can miss at most k vertices, and k-sparses, a defective independent set in which the vertices can be adjacent to at most k vertices, as induced subgraphs. ck(m) is the parameter that gives the maximum graph order n such that all n-graphs can be k-defectively cocolored by using at most m colors. We propose the following results: c0(4) = 12, c1(3) = 12 and c2(2) = 10. We also prove a formula that gives the lower and upper bounds on the ck(m) parameter.