Perfectly contractile graphs and quadratic toric rings

DOI10.1112/BLMS.12789zbMATH Open1521.13040arXiv1911.12345OpenAlexW2991253223MaRDI QIDQ6096783FDOQ6096783

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)

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.

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

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

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)

Cites Work

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