Smallest $C_{2l+1}$-critical graphs of odd-girth $2k+1$

Abstract

Given a graph $H$, a graph $G$ is called $H$-critical if $G$ does not admit a homomorphism to $H$, but any proper subgraph of $G$ does. Observe that $K_{k-1}$-critical graphs are the standard $k$-(colour)-critical graphs. We consider questions of extremal nature previously studied for $k$-critical graphs and generalize them to $H$-critical graphs. After complete graphs, the next natural case to consider for $H$ is that of the odd-cycles. Thus, given integers $\ell$ and $k$, $\ell \ge k$, we ask: what is the smallest order of a $C_{2\ell +1}$-critical graph of odd-girth at least $2k+1$? Denoting this value by $\eta (k,C_{2\ell +1})$, we show that $\eta (k,C_{2\ell +1})=4k$ for $1\le \ell \le k\le \frac{3\ell +i-3}{2}$ ($2k=i\mathrm{mod}3$) and that $\eta (3,C_5)=15$. The latter means that a smallest graph of odd-girth~$7$ not admitting a homomorphism to the $5$-cycle is of order~$15$. Computational work shows that there are exactly eleven such graphs on $15$~vertices of which only two are $C_5$-critical.

16 pages, 8 figures. This version improves upon previous ones and uses the terminology of H-critical graphs, including a slight change of title

References in corpus (3)

• Homomorphism bounds and edge-colourings of $K_4$-minor-free graphs
• Bounds for the smallest $k$-chromatic graphs of given girth
• The width of quadrangulations of the projective plane