The expansion conjecture for critically chromatic graphs

Let G=(V,E)G=(V,E) be a simple graph, where VV is its vertex set. A graph is critically ss-chromatic if it has chromatic number ss and deleting any vertex lowers its chromatic number. For a subset WVW\subseteq V, let G[W]G[W] denote the graph obtained by expanding successively at the vertices in WW, where expansion at a vertex xx adds a new vertex adjacent to xx and to every neighbor of xx. Expansion conjecture. If GG is a critically ss-chromatic graph, then there exists a subset WW of the vertices such that G[W]G[W] is critically (s+1)(s+1)-chromatic. This graph-theoretic conjecture was intended to yield the persistence property for cover ideals of graphs. It was disproved by Kaiser, Stehlík and Škrekovski, who exhibited a family of counterexamples; the paper studies these counterexamples further in relation to persistence and non-increasing depth.

Sources & referencesView supporting material

Primary source

Huy Tai Ha and Mengyao Sun, “Squarefree monomial ideals that fail the persistence property and non-increasing depth”, arXiv:1405.6809 (2014).

Additional references

2 papers in this index state this conjecture (2009–2014). The statement above is taken from the most recent of them; the others are arXiv:0911.1978.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.