On the density of \(C_7\)-critical graphs (Q2151187)

\textit{H. Grötzsch} [Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturwiss. Reihe 6, 697--704, 785--788, 789--798 (1957; Zbl 0089.39506)] proved that every planar graph of girth at least 4 is 3-colorable (or, equivalently, admits a homomorphism to \(C_{3}\)). A generalization of this is the following conjecture: for every positive integer \(t\), every planar graph of girth at least \(4t\) admits a homomorphism to \(C_{2t+1}\). \textit{L. M. Lovász} et al. [J. Comb. Theory, Ser. B 103, No. 5, 587--598 (2013; Zbl 1301.05154)] showed that every \(6t\)-edge connected graph admits a modulo \((2t+1)\)-orientation. This implies that every planar graph of girth at least \(6t\) admits a homomorphism to \(C_{2t+1}\). The authors improve upon this when \(t=3\) by showing that every planar graph of girth at least 16 admits a homomorphism to \(C_{7}\). Using the density of a graph, they first show that for any \(C_{7}\)-critical graph \(G \neq C_{3}, C_{5}\), \(e(G) \geq (17v(G)-2)/15\) which implies that any planar or projective planar graph of girth at least 17 admits a homomorphism to \(C_{7}\). Applying a lemma of \textit{W. Klostermeyer} and \textit{C. Q. Zhang} [J. Graph Theory 33, No. 2, 109--119 (2000; Zbl 0944.05046)] the girth bound can be lowered to 16.