Erdős Problem #944 — Vertex-critical graphs with no small critical edge sets
For a graph , write for its chromatic number, for the graph obtained by deleting a vertex , and for the graph obtained by deleting an edge set . A vertex or edge set is critical if its deletion lowers . A graph with is -vertex-critical if every vertex is critical. The question is: for every pair of integers and , does there exist a graph such that , every vertex of is critical, and every critical edge set has size greater than ? Equivalently, must there exist such a for which
For a vertex-critical graph, deleting one vertex lowers the chromatic number by exactly one, so its vertex condition is also for every . Erdős Problems, Problem 944 Critical edge sets in vertex-critical graphs
Background
Vertex-critical graphs arise naturally in minimal-counterexample arguments for coloring problems: when a graph class is closed under induced subgraphs, a smallest graph in the class whose chromatic number violates a proposed bound must lose chromatic number when any vertex is deleted. Edge-criticality is a related but distinct minimality condition, and Erdős's question asks how resistant a vertex-critical graph can remain to deleting edges. Dirac conjectured in 1970 that for every there is a -vertex-critical graph with no critical edge. Erdős proposed the stronger edge-set question in 1985, asking whether the number of edges that must be deleted to lower the chromatic number can be made arbitrarily large. The case is the exceptional case in both questions. Critical edge sets in vertex-critical graphs Vertex-critical graphs far from edge-criticality
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
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.