The Co-2-plex Polytope and Integral Systems
Benjamin McClosky, Illya V. Hicks · SIAM Journal on Discrete Mathematics · 2009
k-plexes are cohesive subgraphs which were introduced to relax the structure of cliques. A co-k-plex is the complement of a k-plex and is therefore similar to a stable set. This paper derives the co-2-plex analogue for certain properties of the stable set polytope. We also describe a class of 0-1 matrices A for which the polytope $\{x\in\mathbf{R}^n_+\mid Ax\leq 2,$ $x\leq 1\}$ is integral.