Vertex-critical graphs far from edge-criticality

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 $χ(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$.

6 pages