Smallest C₂ + 1-critical graphs of odd-girth 2 k + 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

e l l

and

k

,

e l l g e q k

, we ask: what is the smallest order of a

C_{2 e l l + 1}

-critical graph of odd-girth at least

2 k + 1

? Denoting this value by

e t a (k, C_{2 e l l + 1})

, we show that

e t a (k, C_{2 e l l + 1}) = 4 k

for

1 l e q e l l l e q k l e q f r a c 3 e l l + i - 3 2

(

) and that

e t a (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.

Recommendations

Cites work

Cited in

(2)

Describes a project that uses

Uses Software

This page was built for publication: Smallest \(C_{2 \ell + 1}\)-critical graphs of odd-girth \(2 k + 1\)