## DIMACS TR: 2006-16

## On graphs whose maximal cliques and stable sets intersect

### Authors: Diogo V. Andrade, Endre Boros and Vladimir Gurvich

**
ABSTRACT
**

We say that a graph G has the CIS-property and call G a CIS-graph if
each maximal clique and each maximal stable set of G intersect. By definition,
G is a CIS-graph if and only if the complementary graph $\bar{G}$ is a
CIS-graph too. In this paper we give some necessary and some sufficient
conditions for the CIS-property to hold. In general, problems of efficient
characterization and recognition of CIS-graphs remain open.
Given an integer $k \geq 2$, a comb (or k-comb) S_k is a graph with 2k
vertices k of which, v_1, ..., v_k, form a clique C, while others, v'_1, ...,
v'_k, form a stable set S, and (v_i,v'_i) is an edge for all i = 1, ..., k,
and there are no other edges. The complementary graph $\bar{S_k}$ is called
an anti-comb (or k-anti-comb). Clearly, S and C switch in the complementary
graphs. Obviously, the combs and anti-combs are not CIS-graphs, since
$C \cap S = \emptyset$. Hence, if a CIS-graph G contains an induced comb
(respectively, anti-comb) then it must be settled, that is, G must contain a
vertex $v$ connected to all vertices of C and to no vertex of S.

However, these conditions are only necessary but not sufficient for the
CIS-property to hold. Our main result is the following theorem:
G is a CIS-graph whenever G contains no induced 3-combs and 3-anti-combs,
and every induced 2-comb is settled in G.

We also generalize the concept of CIS-graph as follows. Given intege $d \geq 2$
and a complete graph whose edges are colored by d colors G_d = (V; E_1, ...,
E_d), we say that G_d is a CIS-d-graph (has the CIS-d-property) if
$\bigcap_{i=1}^d C_i \neq \emptyset$ whenever C_i is a maximal color
i-free subset of V, that is, $(v,v') \in E_i$ for no $v, v' \in C_i$. Clearly,
in case $d=2$ we return to the concept of CIS-graphs. It seems that every
CIS-d-graph is a Gallai graph, that is, it cannot contain a triangle colored by
3 distinct colors. We provide partial results in support of this conjecture.
We also show that if this conjecture is true then characterization and
recognition of CIS-d-graphs is easily reduced to characterization and
recognition of CIS-graphs.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2006/2006-16.pdf

DIMACS Home Page