How Difficult Is It to Recognize CIS Graphs?

Rongchuan Tao, Mengxi Yang, Wenan Zang

A graph $G$ is called $CIS$ if each maximal clique intersects each maximal stable set of $G$, with maximality taken with respect to set inclusion. CIS graphs resemble perfect graph…