On the density of C7-critical graphs

Abstract

In 1959, Gr\"{o}tszch famously proved that every planar graph of girth at least 4 admits a homomorphism to $C_3$.  A natural generalization is the following conjecture: for every positive integer $t$, every planar graph of girth at least $4t$ admits a homomorphism to $C_{2t+1}$. This is the planar dual of a well-known conjecture of Jaeger, which states that every $4t$-edge-connected graph admits a modulo $(2t+1)$-orientation. Though Jaeger's original conjecture was recently disproved, it has been shown to hold for $6t$-edge-connected graphs. This implies that every planar graph of girth at least $6t$ admits a homomorphism to $C_{2t+1}$. We improve upon the $t=3$ case, by showing that every planar graph of girth at least $16$ admits a homomorphism to $C_7$.  We obtain this through a more general result regarding the density of critical graphs: if $G$ is a $C_7$-critical graph with $G \not \in \{C_3, C_5\}$, then $e(G) \geq \tfrac{17v(G)-2}{15}$.  Our girth bound is the best known result for Jaeger's Conjecture in the $t=3$ case.