Defective Ramsey Numbers
Presented by Tinaz EKIM
Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs
The classical Ramsey Number R(a; b) is defined as the smallest number n such that all n-graphs contain either a clique of size a or a stable set of size b. It is extremely difficult to compute Ramsey Numbers; despite extensive work, only a few Ramsey Numbers (for small a and b) are known to date. Defective Ramsey Numbers are recently introduced by Ekim and Gimbel where the notion of cliques and stable sets are generalized to respectively k-dense sets and k-sparse sets. Given a graph G and an integer k, a set S of vertices in G is k-sparse if S induces a graph with maximum degree of at most k. Similarly, S is k-dense if S induces a k-sparse graph in the complement of G. We will present some known Defective Ramsey Numbers. Then, we show how these numbers can be used to compute some parameters related to the so-called defective cocoloring problem where one's objective is to minimize the total number of k-dense or k-sparse sets partitioning the vertex set of the given graph. We will also discuss some ongoing research on Defective Ramsey Numbers in some restricted classes of graphs and the related cochromatic parameters.