 |
The co-2-plex polytope: extended formulation and natural-space linear description for certain classes of graphs
1 : LIPN
Université Paris-Nord - Paris XIII
2 : Laboratoire dánalyse et modélisation de systèmes pour láide à la décision
Centre National de la Recherche Scientifique : UMR7243 / FRE3234 / UMR7024, Université Paris Dauphine-PSL, Centre National de la Recherche Scientifique : UMR7024, Centre National de la Recherche Scientifique
3 : Institut de Recherche en Informatique et Systèmes Aléatoires
Université de Rennes, Institut National des Sciences Appliquées - Rennes, Université de Bretagne Sud, École normale supérieure - Rennes, Institut National de Recherche en Informatique et en Automatique, CentraleSupélec, Centre National de la Recherche Scientifique, IMT Atlantique
In a graph, a co-k-plex is a set of nodes inducing a graph in which each node is of degree at most k-1. This is a generalization of stable sets -- that is sets of pairwise nonadjacent nodes -- as these latter correspond to co-1-plexes.
In this talk, we present an extended formulation of the co-2-plex polytope, that is, the convex hull of the incidence vectors of co-2-plexes, when the graph is contraction perfect. We also provide a linear description of the co-2-plex polytope in the natural space for certain classes of graphs, particularly trees.
