Vertex-critical graphs far from edge-criticality
Anders Martinsson, Raphael Steiner · Combinatorics Probability Computing · 2024
Abstract Let $r$ be any positive integer. We prove that for every sufficiently large $k$ there exists a $k$ -chromatic vertex-critical graph $G$ such that $\chi (G-R)=k$ for every set $R \subseteq E(G)$ with $|R|\le r$ . This partially solves a problem posed by Erdős in 1985, who asked whether the above statement holds for $k \ge 4$ .