# On the density of C7-critical graphs

## Main Article Content

## 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.

## Article Details

How to Cite

Postle, L., & Smith-Roberge, E.
(2019).
On the density of C7-critical graphs.

*Acta Mathematica Universitatis Comenianae, 88*(3), 1009-1016. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1260/755
Issue

Section

EUROCOMB 2019