Facets of the bipartite subgraph polytope.

*(English)*Zbl 0578.05056Let \(G=(V,E)\) be an undirected finite graph. For an edge set \(F\subseteq E\) the vector \(x^ F\in R^ E\) with \(x^ F_ e=1\) if \(e\in F\) and \(x^ F_ e=0\) if \(e\not\in F\) is called the incidence vector of \(F\). The bipartite subgraph polytope of the graph \(G\) is then the convex hull in \(R^ E\) of the incidence vectors of all edge sets of bipartite subgraphs of G. The authors obtain for this polytope \(P_ B(G)\) facet defining inequalities with integral coefficients in the interval \([0,n^ 2/4]\) where \(n\) is the order of the given graph \(G\), by showing first that all complete subgraphs of odd order and all so called bicycle wheels contained in \(G\) induce facets of \(P_ B(G)\). New facet defining inequalities of \(P_ B(G)\) are then constructed from known ones by using several methods such as contraction and splitting of nodes, odd subdivisions of the edges and subdivisions of all edges of a cut.

Reviewer: H.Kramer

##### MSC:

05C85 | Graph algorithms (graph-theoretic aspects) |

52B99 | Polytopes and polyhedra |

90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |