Replication in critical graphs and the persistence of monomial ideals

Abstract

Motivated by questions about square-free monomial ideals in polynomial rings, in 2010 Francisco et al. conjectured that for every positive integer k and every k-critical (i.e., critically k-chromatic) graph, there is a set of vertices whose replication produces a (k+1)-critical graph. (The replication of a set W of vertices of a graph is the operation that adds a copy of each vertex w in W, one at a time, and connects it to w and all its neighbours.) We disprove the conjecture by providing an infinite family of counterexamples. Furthermore, the smallest member of the family answers a question of Herzog and Hibi concerning the depth functions of square-free monomial ideals in polynomial rings, and a related question on the persistence property of such ideals.

References in corpus (1)

• Monomial ideals whose depth function has any given number of strict local maxima

Cited by in corpus (6)

• Results on the normality of square-free monomial ideals and cover ideals under some graph operations
• Powers of sums and their associated primes
• On the rigidity of symbolic powers
• A Lower Bound For Depths of Powers of Edge Ideals
• Squarefree monomial ideals that fail the persistence property and non-increasing depth
• Stabilization of associated prime ideals of monomial ideals -- Bounding the copersistence index