Perfectly contractile graphs and quadratic toric rings
arXiv:1911.12345 · doi:10.1112/blms.12789
Abstract
Perfect graphs form one of the distinguished classes of finite simple graphs. In 2006, Chudnovsky, Robertson, Seymour and Thomas proved that a graph is perfect if and only if it has no odd holes and no odd antiholes as induced subgraphs, which was conjectured by Berge. We consider the class of graphs that have no odd holes, no antiholes and no odd stretchers as induced subgraphs. In particular, every graph belonging to is perfect. Everett and Reed conjectured that a graph belongs to if and only if it is perfectly contractile. In the present paper, we discuss graphs belonging to from a viewpoint of commutative algebra. In fact, we conjecture that a perfect graph belongs to if and only if the toric ideal of the stable set polytope of is generated by quadratic binomials. Especially, we show that this conjecture is true for Meyniel graphs, perfectly orderable graphs, and clique separable graphs, which are perfectly contractile graphs.
arXiv comment11 pages, minor revision (typos etc.)
References in corpus (6)
- Theta Bodies for Polynomial Ideals
- A class of perfectly contractile graphs
- Reflexive polytopes arising from perfect graphs
- Toric rings and ideals of stable set polytopes
- Reflexive polytopes arising from partially ordered sets and perfect graphs
- Integer decomposition property for Cayley sums of order and stable set polytopes