DIMACS TR: 2006-16

On graphs whose maximal cliques and stable sets intersect

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


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