A Characterization of Almost CIS Graphs
Yezhou Wu, Wenan Zang, Cun‐Quan Zhang · SIAM Journal on Discrete Mathematics · 2009
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.