Hypergraph Universality and Erdos-Posa Failure for Chromatically Rich Odd Cycles

Abstract

For every fixed $k\ge 3$, every finite nonempty clutter $\mathcal{H}$ can be realized exactly as the family of inclusion-minimal terminal traces of the $k$-bad odd cycles, namely the odd cycles $C$ satisfying $\chi(G[V(C)])\ge k+1$. The host graph $G$ may be chosen $2$-connected, with $T=V(\mathcal{H})$ independent, and with $\chi(G)=k+1$, $\omega(G)=k$, and $|E(G)|\le k|V(G)|$. Given any integer $B\ge 1$, one realization simultaneously preserves the transversal number, the fractional packing number, and every integer $c$-packing number for $1\le c\le B$. Thus chromatic richness on odd-cycle spans has the full packing-covering complexity of arbitrary finite set systems, even in sparse graphs whose chromatic number exceeds their clique number by one. As a consequence, for every $b,N\ge 1$ and every $\varepsilon>0$, there is such a graph with $\tau_k(G)=N$, $\nu_k^{1/c}(G)=c$ for every $1\le c\le b$, and $\nu_k^*(G)<1+\varepsilon$. Hence every finite-congestion and fractional Erd\H{o}s--P\'{o}sa property fails for $k\ge 3$, with an asymptotically optimal fractional obstruction. This contrasts sharply with $k=2$, where the relevant cycles are the ordinary odd cycles: the integral property fails, while Reed's theorem yields every congestion level at least two and the fractional property. We also characterize the shortest $k$-bad odd cycles by a single fixed witness graph.