Normality of cut polytopes of graphs is a minor closed property

Hidefumi Ohsugi

Published 2009-06-29, updated 2009-10-04Version 2

Sturmfels-Sullivant conjectured that the cut polytope of a graph is normal if and only if the graph has no K_5 minor. In the present paper, it is proved that the normality of cut polytopes of graphs is a minor closed property. By using this result, we have large classes of normal cut polytopes. Moreover, it turns out that, in order to study the conjecture, it is enough to consider 4-connected plane triangulations.