Graphs and Matroids Seminar

Title: Density and Structure of Homomorphism-Critical Graphs

Abstract: 

Let H be a graph. A graph G is H-critical if every proper subgraph of G admits a homomor-
phism to H, but G itself does not. In 1981, Jaeger made the following conjecture concerning
odd-cycle critical graphs: every planar graph of girth at least 4t admits a homomorphism to
C_2t+1 (or equivalently, has a (2t+1)/t -circular colouring). The best known result for the t = 3 case
states that every planar graph of girth at least 18 has a homomorphism to C₇. We improve
upon this result, showing that every planar graph of girth at least 16 admits a homomorphism
to C₇. This is obtained from a more general result regarding the density of C₇-critical graphs.
Our main theorem is that if G is a C₇-critical graph with G ∉ {C_3,C₅}, then e(G) ≥ [17v(G)-2]/15 .
In this talk, I will go over the history of the progress towards Jaeger's conjecture, and give
a general overview of the proof structure of our main theorem. Along the way, I will prove
several structural lemmas concerning graphs that are H-critical, when H is a vertex-transitive
non-bipartite graph.