×

Smallest \(C_{2l+1}\)-critical graphs of odd-girth \(2k+1\). (English) Zbl 1456.05117

Changat, Manoj (ed.) et al., Algorithms and discrete applied mathematics. 6th international conference, CALDAM 2020, Hyderabad, India, February 13–15, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12016, 184-196 (2020).
Summary: 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 classic \(k\)-(colour)-critical graphs. This work is a first step towards extending questions of extremal nature from \(k\)-critical graphs to \(H\)-critical graphs. Besides complete graphs, the next classic case is odd cycles. Thus, given integers \(l\ge k\) we ask: what is the smallest order \(\eta(k,l)\) of a \(C_{2l+1}\)-critical graph of odd-girth at least \(2k+1\)? Denoting this value by \(\eta (k,l)\), we show that \(\eta (k,l)=4k\) for \(l\le k\le \frac{3l+i-3}{2}\) \((2k=i\bmod 3)\) and that \(\eta (3,2)=15\). The latter is to say that a smallest graph of odd-girth 7 not admitting a homomorphism to the 5-cycle is of order 15 (there are at least 10 such graphs on 15 vertices).
For the entire collection see [Zbl 1435.68020].

MSC:

05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
PDFBibTeX XMLCite
Full Text: DOI