Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1016/j.disc.2009.11.012 | Discrete Mathematics |
Keywords | Field | DocType |
cut polytope,normal polytope | Cut,Normality,Discrete mathematics,Combinatorics,Normal polytope,K-tree,Minimum cut,Polytope,Conjecture,Mathematics,Maximum cut | Journal |
Volume | Issue | ISSN |
310 | 6-7 | Discrete Mathematics |
Citations | PageRank | References |
6 | 0.75 | 3 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Hidefumi Ohsugi | 1 | 27 | 10.42 |