On the density of C7-critical graphs
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 1009-1016
Citer cet article
Voir la notice de l'article provenant de la source Comenius University
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.