Perfectly contractile graphs and quadratic toric rings

DOI10.1112/BLMS.12789MaRDI QIDQ6096783zbMATH OpenOpenAlexFDO

Authors Hidefumi Ohsugi, Kazuki Shibata, Akiyoshi Tsuchiya

Publication date 15 September 2023

Published in Bulletin of the London Mathematical Society (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1911.12345

Mathematics Subject Classification ID

Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Perfect graphs (05C17)

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 $mathcalA$ of graphs that have no odd holes, no antiholes and no odd stretchers as induced subgraphs. In particular, every graph belonging to $mathcalA$ is perfect. Everett and Reed conjectured that a graph belongs to $mathcalA$ if and only if it is perfectly contractile. In the present paper, we discuss graphs belonging to $mathcalA$ from a viewpoint of commutative algebra. In fact, we conjecture that a perfect graph $G$ belongs to $mathcalA$ if and only if the toric ideal of the stable set polytope of $G$ 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.

Recommendations

• scientific article; zbMATH DE number 3887724
• Perfectly contractile diamond-free graphs
• A class of perfectly contractile graphs
• Path parity and perfection
• Progress on perfect graphs

Cites work

• scientific article; zbMATH DE number 3168327 (Why is no real title available?)
• A class of perfectly contractile graphs
• A fast algorithm for coloring Meyniel graphs
• Almost all Berge Graphs are Perfect
• Binomial ideals
• Bull-free weakly chordal perfectly orderable graphs
• Chain polytopes and algebras with straightening laws
• Compressed polytopes and statistical disclosure limitation
• Convex polytopes all of whose reverse lexicographic initial ideals are squarefree
• Graph Classes: A Survey
• Ideals of graph homomorphisms
• Integer decomposition property for Cayley sums of order and stable set polytopes
• Koszul bipartite graphs
• Meyniel weakly triangulated graphs. I: Co-perfect orderability
• Non-Koszul quadratic Gorenstein toric rings
• On a conjecture of Meyniel
• On certain polytopes associated with graphs
• On dart-free perfectly contractile graphs
• On planar perfectly contractile graphs
• On the structure of bull-free perfect graphs
• Perfectly contractile graphs
• Perfectly orderable graphs and almost all perfect graphs are kernel \(M\)- solvable
• Reflexive polytopes arising from partially ordered sets and perfect graphs
• Reflexive polytopes arising from perfect graphs
• Reverse lexicographic squarefree initial ideals and Gorenstein Fano polytopes
• The strong perfect graph theorem
• Theta bodies for polynomial ideals
• Topics on perfect graphs

Cited in

(1)

• Toric rings of perfectly matchable subgraph polytopes

This page was built for publication: Perfectly contractile graphs and quadratic toric rings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6096783)