Density and Structure of Homomorphism-Critical Graphs

homomorphism;circular colouring;graph theory;potential method;discharging;circular flow conjecture;odd cycle;critical

Smith-Roberge, Evelyneaffiliation1:Faculty of Mathematics ; advisor:Postle, Luke ; Postle, Luke ;

University of Waterloo

关键词: odd cycle;    discharging;    circular flow conjecture;    Master Thesis;    critical;    graph theory;    potential method;    homomorphism;    circular colouring;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/13643/1/Smith-Roberge_Evelyne.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

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 $C_{2t+1}$ (or equivalently, has a $frac{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_7$. We improve upon this result, showing that every planar graph of girth at least 16 admits a homomorphism to $C_7$. This is obtained from a more general result regarding the density of $C_7$-critical graphs. Our main result is that if $G$ is a $C_7$-critical graph with $G ot in {C_3, C_5}$, then $e(G) geq frac{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.