← All problems

Erdős Problem #944 — Vertex-critical graphs with no small critical edge sets

41 years old · traced to

For a graph GG, write χ(G)\chi(G) for its chromatic number, G−vG-v for the graph obtained by deleting a vertex vv, and G−RG-R for the graph obtained by deleting an edge set R⊆E(G)R\subseteq E(G). A vertex or edge set is critical if its deletion lowers χ(G)\chi(G). A graph with χ(G)=k\chi(G)=k is kk-vertex-critical if every vertex is critical. The question is: for every pair of integers k≥4k\geq 4 and r≥1r\geq 1, does there exist a graph GG such that χ(G)=k\chi(G)=k, every vertex of GG is critical, and every critical edge set has size greater than rr? Equivalently, must there exist such a GG for which

χ(G−R)=kfor every R⊆E(G) with ∣R∣≤r?\chi(G-R)=k\qquad\text{for every }R\subseteq E(G)\text{ with }|R|\leq r?

For a vertex-critical graph, deleting one vertex lowers the chromatic number by exactly one, so its vertex condition is also χ(G−v)=k−1\chi(G-v)=k-1 for every v∈V(G)v\in V(G). 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 k≥4k\geq4 there is a kk-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 k=4k=4 is the exceptional case in both questions. Critical edge sets in vertex-critical graphs Vertex-critical graphs far from edge-criticality

References

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.