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