On the Density of C₇-Critical Graphs

DOI10.1007/S00493-020-4177-YMaRDI QIDQ6315418arXivFDO

Authors Luke Postle, Evelyne Smith-Roberge

Publication date 11 March 2019

Published in arXiv

Full work available at URL https://doi.org/10.1007/S00493-020-4177-Y

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

arXiv classification

math.CO

Abstract: In 1959, Gr"{o}tzsch famously proved that every planar graph of girth at least 4 is 3-colourable (or equivalently, admits a homomorphism to $C_3$). A natural 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}$. This is in fact 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 disproved in 2018 by Han et al., Lovasz et al. showed that every $6t$-edge connected graph admits a modulo $(2t+1)$-flow. The latter result implies that every planar graph of girth at least $6t$ admits a homomorphism to $C_{2t+1}$. We improve upon this in 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 $C_7$-critical graphs: if $G$ is a $C_7$-critical graph with $Gotin{C}_3,C_5$, then $e(G)geqfrac17v(G)-215$.

This page was built for publication: On the Density of $C_7$-Critical Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6315418)