On split and almost CIS-graphs.
Endre Boros, Vladimir A. Gurvich, Igor É. Zverovich · 2009
A CIS-graph is defined as a graph whose every maximal clique and stable set intersect. These graphs have many interesting properties, yet, it seems difficult to obtain an efficient characterization and/or polynomial-time recognition algorithm for CIS-graphs. An almost CIS-graph is defined as a graph that has a unique pair (C, S) of disjoint maximal clique C and stable sets S. We conjecture that almost CIS-graphs are exactly split graphs that have a unique split partition and prove this conjecture for a large hereditary class of graphs that contains, for example, chordal graphs and P5-free graphs, as well as their complements, etc. We also prove the conjecture in case |C = |S| =2 and show that the vertex-set R = V \\ (C ∪ S) cannot induce a threshold graph, although we do not prove that R = ∅, as the conjecture suggests.