Binomial edge ideals of cographs

Abstract

We determine the Castelnuovo-Mumford regularity of binomial edge ideals of complement reducible graphs (cographs). For cographs with $n$ vertices the maximum regularity grows as $2n/3$. We also bound the regularity by graph theoretic invariants and construct a family of counterexamples to a conjecture of Hibi and Matsuda.

11 pages, 2 figures. v2: Final version as in Revista de la Unión Matemática Argentina