turkmath.org

In extremal graph theory, $R(i,j)$ is defined as the smallest integer $n$ such that any simple undirected graph on $n$ vertices has either a clique of size $i$ or an independent set of size $j$, and $c(m)$ is defined as the greatest integer $r$ such that every graph on $r$ vertices can be partitioned into $m$ subsets where each subset induces either a clique or an independent set. These parameters are well-studied in the literature, but their exact values are known only for smaller values of $i$, $j$, $m$. However, it may be possible to find exact formulas for $R(i,j)$ and $c(m)$ when they are examined on some graph classes such as perfect graphs.

As a relaxation of the notions clique and independent set, one can define \textit{$k$-defective} sets. A \textit{$k$-sparse $i$-set} is a set $S$ of $i$ vertices of a graph $G$ such that each vertex in $S$ has degree at most $k$ in $G$. Similarly, a \textit{$k$-dense $j$-set} is a set $D$ of $j$ vertices of a graph $G$ such that each vertex in $D$ has degree at most $k$ in the complement of $G$; in other words, each vertex in $D$ misses at most $k$ other vertices in its neighborhood. The term $k-$defective is used to denote a $k$-sparse or $k$-dense set, and note that $0$-dense and $0$-sparse sets correspond to cliques and independent sets, respectively.

Let $R_k^{\mathcal{G}}(i,j)$ be the smallest natural number $n$ such that every graph in the class $\mathcal{G}$ on $n$ vertices has either a $k$-dense $i$-set or a $k$-sparse $j$-set, and $c_k^{\mathcal{G}}(m)$ be greatest integer $r$ such that every graph in the class $\mathcal{G}$ on $r$ vertices can be partitioned into $m$ subsets where each subset induces a $k$-defective set. The talk will be about some partial results on $R_k^{\mathcal{G}}(i,j)$ and $c_k^{\mathcal{G}}(m)$ when $\mathcal{G}$ represents perfect graphs, or some of its subclasses such as cographs and split graphs.

This is joint work with T{\i}naz Ekim, John Gimbel and Yunus Emre Demirci.