Completely separable graphs

AbstractWe define a property of Boolean functions called separability, and specialize it for a class of functions naturally associated with graphs. “Completely separable graphs” are then derived and characterized in particular by the existence of two crossing chords in any cycle of length at least five. This implies that completely separable graphs are perfect. We present linear time algorithms for the recognition and for the usual optimization problems (maximum weighted stable set and maximum weighted clique)