The expansion conjecture for critically chromatic graphs
The expansion conjecture for critically chromatic graphs
Let be a simple graph, where is its vertex set. A graph is critically -chromatic if it has chromatic number and deleting any vertex lowers its chromatic number. For a subset , let denote the graph obtained by expanding successively at the vertices in , where expansion at a vertex adds a new vertex adjacent to and to every neighbor of . Expansion conjecture. If is a critically -chromatic graph, then there exists a subset of the vertices such that is critically -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.