19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

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.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors