# zbMATH — the first resource for mathematics

Facets of the bipartite subgraph polytope. (English) Zbl 0578.05056
Let $$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
Full Text: