Back to search

University of Waterloo

Density and Structure of Homomorphism-Critical Graphs

Abstract

dc:description.abstract

Let $H$ be a graph. A graph $G$ is $H$-critical if every proper subgraph of $G$ admits a homomorphism 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 C2t+1 (or equivalently, has a $\tfrac{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 C7. We improve upon this result, showing that every planar graph of girth at least 16 admits a homomorphism to C7. This is obtained from a more general result regarding the density of C7-critical graphs. Our main result is that if $G$ is a C7-critical graph with G \not \in \{C3, C5\}, then $e(G) \geq \tfrac{17v(G)-2}{15}$. Additionally, we prove several structural lemmas concerning graphs that are $H$-critical, when $H$ is a vertex-transitive non-bipartite graph.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Smith-Roberge, Evelyne
Advisor dc:contributor.advisor
  • Postle, Luke

Subjects

dc:subject × 8

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/13643

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Smith-Roberge, Evelyne. Density and Structure of Homomorphism-Critical Graphs. University of Waterloo, 2018. http://hdl.handle.net/10012/13643