• A
• A
• A
• ABC
• ABC
• ABC
• Π
• Π
• Π
• Π
• Π
Regular version of the site

## Smallest πΆ_{2π+1}-Critical Graphs of Odd-Girth 2π+1

P. 184-196.
Beaudou L., Foucaud F., Naserasr R.

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 πΎπ−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 ππ we ask: what is the smallest order π(π,π) of a πΆ2π+1-critical graph of odd-girth at least 2π+1? Denoting this value by π(π,π), we show that π(π,π)=4π for ππ≤3π+π−32 (2π=πmod3) and that π(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).