In graph theory, a homomorphism is a vertex mapping that preserves adjacency: if two vertices are connected in graph $G$, their images must be connected in graph $H$. Standard graph coloring is simply a homomorphism where the target $H$ is a complete graph $K_k$. However, a more nuanced structural theory emerges when we replace the target $K_k$ with an odd cycle $C_{2\ell+1}$.
Foucaud et al. and Beaudou et al. explore the boundaries of this mapping through the lens of $H$-criticality. A graph $G$ is $H$-critical if $G$ itself cannot be mapped to $H$, but every one of its proper subgraphs can. These graphs represent the "minimal obstructions" that prevent a homomorphism from existing.
The Tension Between Girth and Homomorphism
The difficulty of mapping a graph $G$ to an odd cycle $C_{2\ell+1}$ is intrinsically linked to the length of the shortest odd cycle in $G$, known as its odd-girth. Intuitively, if $G$ only contains very long odd cycles, it should be "easier" to map it to a shorter odd cycle. For example, any graph with no odd cycles (a bipartite graph) can be mapped to a single edge.
The research direction pursued by the authors asks a fundamental extremal question: given a target odd cycle $C_{2\ell+1}$ and a requirement that $G$ has a minimum odd-girth of $2k+1$, what is the smallest possible number of vertices $G$ can have while remaining $C_{2\ell+1}$-critical?
This value, denoted $\eta(k, C_{2\ell+1})$, serves as a benchmark for the complexity of graph structures. If a graph is smaller than this bound, its odd-girth alone might guarantee that a homomorphism exists.
Structural Obstructions and Odd-K4s
To understand why a graph might fail to map to an odd cycle, the authors rely on the structural properties of subdivisions. A key result in this area is a theorem by Gerards, which states that if a graph lacks an odd-$K_4$—a specific subdivision of the complete graph $K_4$ where each face is an odd cycle—it must admit a homomorphism to its shortest odd cycle.
This theorem provides the "engine" for constructing and proving the minimality of critical graphs. To be $C_{2\ell+1}$-critical, a graph must contain enough structural complexity (like an odd-$K_4$) to block the homomorphism, but it must be constructed so that removing any edge destroys that complexity.
Beaudou et al. leverage these subdivisions to show that for many cases, the minimum order of these critical graphs is surprisingly small, specifically $4k$. This suggests that the "minimal" way to block a homomorphism while maintaining a high odd-girth is to build a tightly constrained, symmetric structure around these forbidden subdivisions.
Benchmarking Complexity
The authors provide concrete bounds for specific cases that highlight the jump in complexity as constraints tighten. In Smallest C2l+1-Critical Graphs of Odd-Girth 2k+1, the authors identify that for $C_5$-critical graphs with a minimum odd-girth of 7, the smallest possible order is 15.
This result is significant because it distinguishes $H$-criticality from standard color-criticality. While triangle-free 4-chromatic graphs (which are $K_3$-critical) can be relatively small, requiring a graph to be critical relative to a 5-cycle with an even larger odd-girth forces the vertex count to rise significantly. The authors found that while eleven non-isomorphic graphs of order 15 satisfy the odd-girth and mapping constraints, only two are strictly $C_5$-critical, meaning they are the unique minimal "reasons" why such a mapping fails.
By determining these exact values, the authors provide a map of the landscape of graph homomorphisms, showing how local constraints like girth and global constraints like target-graph mappings interact to dictate the necessary size of a graph.
Key Foundational Work
Smallest C2ℓ+1-critical graphs of odd-girth 2k+1 (2022) — contributed 10 concept elements to this direction.
Smallest C2l+1-Critical Graphs of Odd-Girth 2k+1 (2020) — contributed 6 concept elements to this direction.