Vertex-critical graphs far from edge-criticality

Anders Martinsson, Raphael Steiner

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 \subset…