Replication in critical graphs and the persistence of monomial ideals

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:123

Article

Kaiser, Tomas^1,2  Stehlik, Matej³  Skrekovski, Riste^4,5,6 

[1] Univ W Bohemia, Dept Math, Inst Theoret Comp Sci CE ITI, Plzen 30614, Czech Republic

[2] Univ W Bohemia, European Ctr Execllence NTIS, New Technol Informat Soc, Plzen 30614, Czech Republic

[3] UJF Grenoble 1 CNRS Grenoble INP, G SCOP UMR5272, F-38031 Grenoble, France

[4] Univ Ljubljana, Dept Math, Ljubljana, Slovenia

[5] Fac Informat Studies, Novo Mesto, Slovenia

[6] Univ Primorska, FAMNIT, Koper, Slovenia

关键词: Critical graph;    Replication;    Cover ideal;    Square-free monomial ideal;    Associated prime;    Persistence property;   

DOI  :  10.1016/j.jcta.2013.12.005

来源: Elsevier

【 摘 要 】

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. (C) 2013 Elsevier Inc. All rights reserved.

【 授权许可】

Free