Codegree and regularity of stable set polytopes
Abstract
The codegree codeg ( π« ) of a lattice polytope π« is a fundamental invariant in discrete geometry. In the present paper, we investigate the codegree of the stable set polytope π« G associated with a simple graph G . Specifically, we establish the inequalities Ο ( G ) + 1 β€ codeg ( π« G ) β€ Ο ( G ) + 1 , where Ο ( G ) and Ο ( G ) denote the clique number and the chromatic number of G , respectively. Furthermore, an explicit formula for codeg ( π« G ) is given when G is either a line graph or an h -perfect graph. Finally, as an application of these results, we provide upper and lower bounds on the regularity of the toric ring associated with π« G .
Fields of Study & Subjects
Advanced Optimization Algorithms Research
Commutative Algebra and Its Applications
Optimization and Variational Analysis
Publication details
- Journal / source
- Algebraic Combinatorics
- Volume
- 8
- Issue
- 6
- Pages
- 1743β1751
- Publication date
- 6 January 2026
- Language
- EN