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.
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.
Status
- Refuted: Tomáš Kaiser, Martin Stehlík and Riste Škrekovski. Replication in critical graphs and the persistence of monomial ideals (arXiv, 2013) https://arxiv.org/abs/1301.6983
Source: Huy Tai Ha and Mengyao Sun, “Squarefree monomial ideals that fail the persistence property and non-increasing depth”, arXiv:1405.6809 (2014).
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
No solutions have been posted yet.