The expansion conjecture for critically chromatic graphs
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.