Quadrangulations and 4-color-critical graphs (Q1826961)

A graph is \(k\)-critical if its chromatic number is \(k\), but the chromatic number of every proper subgraph is smaller than \(k\). It is know that every nonbipartite quadrangulation of the projective plane has chromatic number 4 [\textit{D. A. Youngs}, J. Graph Theory 21, No. 2, 219--227 (1996; Zbl 0839.05040)]. \textit{J. Gimbel} and \textit{C. Thomassen} [Trans. Am. Math. Soc. 349, No. 11, 4555--4564 (1997; Zbl 0884.05039)] proved that such quadrangulations are 4-critical if every 4-cycle bounds a face. These graphs are used to answer two questions about 4-critical graphs asked by Erdős and by Erdős and Hajnal in the 1970s. More precisely, there exist arbitrarily large 4-critical graphs that can be made bipartite by deleting just four edges. Also, there are 4-critical graphs \(G_n\) of arbitrarily large orders \(n\), such that in every subgraph \(H\) of \(G_n\), there is a set of at most \(4| V(H)| / \sqrt{n}\) edges whose removal from \(H\) results in a bipartite graph.