## DIMACS TR: 2009-10

## A Characterization of Almost CIS Graphs

### Authors: Yezhou Wu, Wenan Zang and Cun-Quan Zhang

**
ABSTRACT
**

A graph G is called CIS if each maximal clique intersects each maximal
stable set in G, and is called almost CIS if it has a unique disjoint pair (C; S)
consisting of a maximal clique C and a maximal stable set S. While it is still
unknown if there exists a good structural characterization of all CIS graphs, in this
note we prove the following Andrade-Boros-Gurvich conjecture: A graph is almost
CIS if and only if it is a split graph with a unique split partition.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2009/2009-10.pdf

DIMACS Home Page