Smallest not C_2l+1-colourable graphs of odd-girth 2k+1[This work is supported by the IFCAM project Applications of graph homomorphisms (MA/IFCAM/18/39) and by the ANR project HOSIGRA (ANR-17-CE40-0022).]

Laurent Beaudou[LIMOS, Université Clermont Auvergne, Aubière (France). E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS>Florent Foucaud[2]
Reza Naserasr[CNRS - IRIF, Université Paris Diderot, Paris (France). E-mail<EMAIL_ADDRESS>
Grötzsch introduced his famous graph as a triangle-free graph which is not 3-colourable. Harary showed that any such graph must be of order at least 11 and Chvátal proved that the Grötzsch graph is the only such graph on 11 vertices.
As a generalization, Ngoc and Tuza asked about the order of a smallest graph of odd-girth $2k+1$ which is not 3-colourable, a question which, despite several partial results, remains open.

Viewing 3-colouring as a homomorphism to the 3-cycle, along this line of work, we ask more generally: What is the smallest order $\eta(k,l)$ of a graph of odd-girth $2k+1$ that admits no homomorphism to the cycle $C_{2l+1}$?

In this work, we determine the value of $\eta(k,l)$ for $l\leq k\leq\frac{3l+i-3}{2}$ ($2k=i\bmod 3$)  and for $(k,l)=(3,2)$. More precisely, we show that $\eta(k,l)$=$4k$ for $l\leq k\leq\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 10 such graphs on 15 vertices).

§ INTRODUCTION

A homomorphism of a graph $G$ to a graph $H$ is a vertex-mapping that preserves adjacency, i.e., a mapping $\psi:V(G) \to V(H)$ such that if $x\sim y$ in $G$, then $\psi(x)\sim \psi(y)$ in $H$. If there exists a homomorphism of $G$ to $H$, we may write $G \to H$ and we may say that $G$ is $H$-colourable. In the study of homomorphisms, it is usual to work with the core of a graph. That is, a minimal subgraph which admits a homomorphism from the graph itself. It is not difficult to show that a core of a given graph is unique up to isomorphism. A graph is said to be a core if it admits no homomorphism to a proper subgraph. We refer to the book [10] on graph homomorphisms for a reference.

It is easy to check that $G$ is $K_k$-colourable (where $K_k$ is a complete graph on $k$ vertices) if and only if $G$ is (properly) $k$-colourable. The problem of $K_k$-colourability is among the most studied questions in graph theory.

Another family of graphs for which the $H$-colouring problem is of high importance is the family of odd-cycles. We refer to this as $C_{2l+1}$-colourability, where $C_i$ is the cycle of length $i$. $C_{2l+1}$-colourability is directly related to circular and fractional colouring of graphs, see [10]. Many other interesting questions are formulated, or reformulated, in the language of $C_{2l+1}$-colourability, for example, the Jaeger-Zhang conjecture [22] (see also [3, 23]) and the Pentagon Conjecture of Nešetřil [13].

On the other hand, the question of building graphs of high girth or high odd-girth and high chromatic number is a part of classic graph theory that is still a subject of high interest. As one of the earliest results on the subject, Grötzsch built a graph on 11 vertices (see Figure <ref>(i)) which is triangle-free (i.e. of odd-girth $\geq 5$) and not mapping to $K_3$ (i.e. not 3-colourable).  Harary [9] showed that 11 vertices are needed to build any such graph, and Chvátal [4] showed that the Grötzsch graph is the only such graph on 11 vertices. Along this line of work, and viewing $K_3$ as an odd-cycle of length $3$ we ask the following general question.

Given positive integers $k,l$, what is the smallest order $\eta(k,l)$ of a graph of odd-girth $2k+1$ that admits no homomorphism to $C_{2l+1}$?

Note that whenever $k<l$, we have $\eta(k,l)=2k+1$ since $C_{2k+1}$ itself provides the answer to Problem <ref>. Clearly, $\eta(1,1)=4$ since $K_4$ is the smallest graph that is not $3$-colourable. With this terminology, the result of Harary can be restated as $\eta(2,1)=11$. For $l=1$ and arbitrary $k$, Problem <ref> asks for the smallest order of a graph of odd-girth $2k+1$ that is not $3$-colourable. This question, asked in a different formulation by Ngoc and Tuza in [15],  has gained a lot of attention. The best known upper bound comes from a generalization of the Grötzsch graph, known as the generalized $k$-level Mycielski graph of $C_{2k+1}$ (denoted $M_{k}(C_{2k+1})$) which was defined independently in [14] and [19]. This is a $4$-chromatic graph of odd-girth $2k+1$ which is constructed as follows: $V(M_{k}(C_{2k+1}))=V_1\cup\ldots\cup V_{k}\cup\{v\}$, where $V_i=\{u^i_0,\ldots,u^i_{2k}\}$ for $1\leq i\leq k$. The first level, $V_1$, induces a $(2k+1)$-cycle $u^1_0,\ldots,u^1_{2k}$. For each level $V_i$ with $2\leq i\leq k$, vertex $u^i_j$ is adjacent to the two vertices $u^{i-1}_{(j-1)\bmod 2k+1}$ and $u^{i-1}_{(j+1)\bmod 2k+1}$ in the level $V_{i-1}$. Finally, vertex $v$ is adjacent to all vertices in $V_{k}$. Thus, $M_2(C_{5})$ is simply the classic Mycielski construction for $C_5$, that is, the Grötzsch graph. See Figure <ref> for the first three examples.

Several authors (starting with Payan [17]) showed that $M_{k}(C_{2k+1})$ is $4$-chromatic for any $k\geq 1$, implying that $\eta(k,1)\leq 2k^2+k+1$. We refer to [8, 15, 20, 21] for several other proofs. Among these authors, Ngoc and Tuza [15] asked whether this upper bound of $2k^2+k+1$ is essentially optimal. The best known lower bound to this date is due to Jiang [11], who proved (by a modification of a proof by Nilli [16]) that $\eta(k,1)\geq (k-1)^2+2$, and thus $\eta(k,1)=\Theta(k^2)$. Recently, Esperet and Stehlík [5] proved that $\eta(k,1)=2k^2+k+1$ for graphs where any two odd-cycles have a common vertex.[In fact, Ngoc and Tuza [15] equivalently asked for the value of the smallest constant $c$ such that the odd-girth of any $4$-chromatic graph of order $n$ is at most $(c+o(1))\sqrt{n}$. In this language, the tentative value $\eta(k,1)=2k^2+k+1$ translates to a value of $\sqrt{2n-7/4} + 1/2$ for the odd-girth of a $4$-chromatic graph of order $n$; this is also the formulation used in [5]. The result of Jiang [11] is formulated as a strict upper bound of $2\sqrt{n}+3$ for the odd-girth of a $4$-chromatic graph of order $n$.] The authors of this article, in joint work with Gordon Royle, also study this problem in a forthcoming paper [2].

[$M_{2}(C_5)$]0.6[join=bevel,inner sep=0.6mm]

at (0,-3) ;
[draw,shape=circle,fill] (x0) at (18:1.5) ;
[draw,shape=circle,fill] (x1) at (90:1.5) ;
[draw,shape=circle,fill] (x2) at (162:1.5) ;
[draw,shape=circle,fill] (x3) at (234:1.5) ;
[draw,shape=circle,fill] (x4) at (306:1.5) ;
[-,line width=0.4mm] (x0)–(x1)–(x2)–(x3)–(x4)–(x0);

[draw,shape=circle,fill] (y0) at (18:0.75) ;
[draw,shape=circle,fill] (y1) at (90:0.75) ;
[draw,shape=circle,fill] (y2) at (162:0.75) ;
[draw,shape=circle,fill] (y3) at (234:0.75) ;
[draw,shape=circle,fill] (y4) at (306:0.75) ;
[-,line width=0.4mm] (x4)–(y0)–(x1)

[draw,shape=circle,fill] (0) at (0,0) ;
[-,line width=0.4mm] (y0)–(0)–(y1) (y2)–(0)–(y3)  (y4)–(0);
[$M_{3}(C_7)$]0.6[join=bevel,inner sep=0.6mm]

at (0,-3) ;

[draw,shape=circle,fill] (x0) at (-13:2.25) ;
[draw,shape=circle,fill] (x1) at (38:2.25) ;
[draw,shape=circle,fill] (x2) at (90:2.25) ;
[draw,shape=circle,fill] (x3) at (141:2.25) ;
[draw,shape=circle,fill] (x4) at (192:2.25) ;
[draw,shape=circle,fill] (x5) at (244:2.25) ;
[draw,shape=circle,fill] (x6) at (295:2.25) ;

[-,line width=0.4mm] (x0)–(x1)–(x2)–(x3)–(x4)–(x5)–(x6)–(x0);

[draw,shape=circle,fill] (y0) at (-13:1.5) ;
[draw,shape=circle,fill] (y1) at (38:1.5) ;
[draw,shape=circle,fill] (y2) at (90:1.5) ;
[draw,shape=circle,fill] (y3) at (141:1.5) ;
[draw,shape=circle,fill] (y4) at (192:1.5) ;
[draw,shape=circle,fill] (y5) at (244:1.5) ;
[draw,shape=circle,fill] (y6) at (295:1.5) ;
[-,line width=0.4mm] (x6)–(y0)–(x1)

[draw,shape=circle,fill] (z0) at (-13:0.75) ;
[draw,shape=circle,fill] (z1) at (38:0.75) ;
[draw,shape=circle,fill] (z2) at (90:0.75) ;
[draw,shape=circle,fill] (z3) at (141:0.75) ;
[draw,shape=circle,fill] (z4) at (192:0.75) ;
[draw,shape=circle,fill] (z5) at (244:0.75) ;
[draw,shape=circle,fill] (z6) at (295:0.75) ;
[-,line width=0.4mm] (y6)–(z0)–(y1)

[draw,shape=circle,fill] (0) at (0,0) ;
[-,line width=0.4mm] (z0)–(0)–(z1) (z2)–(0)–(z3)  (z4)–(0)–(z5) (z6)–(0);

[$M_{4}(C_9)$]0.6[join=bevel,inner sep=0.6mm]

[draw,shape=circle,fill] (x0) at (10:3) ;
[draw,shape=circle,fill] (x1) at (50:3) ;
[draw,shape=circle,fill] (x2) at (90:3) ;
[draw,shape=circle,fill] (x3) at (130:3) ;
[draw,shape=circle,fill] (x4) at (170:3) ;
[draw,shape=circle,fill] (x5) at (210:3) ;
[draw,shape=circle,fill] (x6) at (250:3) ;
[draw,shape=circle,fill] (x7) at (290:3) ;
[draw,shape=circle,fill] (x8) at (330:3) ;

[-,line width=0.4mm] (x0)–(x1)–(x2)–(x3)–(x4)–(x5)–(x6)–(x7)–(x8)–(x0);

[draw,shape=circle,fill] (y0) at (10:2.25) ;
[draw,shape=circle,fill] (y1) at (50:2.25) ;
[draw,shape=circle,fill] (y2) at (90:2.25) ;
[draw,shape=circle,fill] (y3) at (130:2.25) ;
[draw,shape=circle,fill] (y4) at (170:2.25) ;
[draw,shape=circle,fill] (y5) at (210:2.25) ;
[draw,shape=circle,fill] (y6) at (250:2.25) ;
[draw,shape=circle,fill] (y7) at (290:2.25) ;
[draw,shape=circle,fill] (y8) at (330:2.25) ;
[-,line width=0.4mm] (x8)–(y0)–(x1)

[draw,shape=circle,fill] (z0) at (10:1.5) ;
[draw,shape=circle,fill] (z1) at (50:1.5) ;
[draw,shape=circle,fill] (z2) at (90:1.5) ;
[draw,shape=circle,fill] (z3) at (130:1.5) ;
[draw,shape=circle,fill] (z4) at (170:1.5) ;
[draw,shape=circle,fill] (z5) at (210:1.5) ;
[draw,shape=circle,fill] (z6) at (250:1.5) ;
[draw,shape=circle,fill] (z7) at (290:1.5) ;
[draw,shape=circle,fill] (z8) at (330:1.5) ;
[-,line width=0.4mm] (y8)–(z0)–(y1)

[draw,shape=circle,fill] (t0) at (10:0.75) ;
[draw,shape=circle,fill] (t1) at (50:0.75) ;
[draw,shape=circle,fill] (t2) at (90:0.75) ;
[draw,shape=circle,fill] (t3) at (130:0.75) ;
[draw,shape=circle,fill] (t4) at (170:0.75) ;
[draw,shape=circle,fill] (t5) at (210:0.75) ;
[draw,shape=circle,fill] (t6) at (250:0.75) ;
[draw,shape=circle,fill] (t7) at (290:0.75) ;
[draw,shape=circle,fill] (t8) at (330:0.75) ;
[-,line width=0.4mm] (z8)–(t0)–(z1)

[draw,shape=circle,fill] (0) at (0,0) ;
[-,line width=0.4mm] (t0)–(0)–(t1) (t2)–(0)–(t3) (t4)–(0)–(t5) (t6)–(0)–(t7) (t8)–(0);

Three examples of generalized Mycielski constructions.

In this paper, we study Problem <ref> when $l\geq 2$. As we discuss later (see Section <ref>), it follows from a theorem of Gerards [6] that $\eta(k,l)\geq 4k$ whenever $l\leq k$, and $\eta(k,k)=4k$. We prove (in Section <ref>) that, surprisingly, $\eta(k,l)=4k$ whenever $l\leq k\leq\frac{3l+i-3}{2}$ (with $2k=i\bmod 3$). We then prove (in Section <ref>) that $\eta(3,2)=15$. We conclude with further research questions in the last section.

The value of $\eta(3,2)$ indeed was the initial motivation of this work. In [1], we use the fact that $\eta(3,2)=15$ to prove that if a graph $B$ of odd-girth $7$ has the property that any series-parallel graph of odd-girth $7$ admits a homomorphism to it, then it has at least $15$ vertices.

Table <ref> summarizes the known bounds for Problem <ref> and small values of $k$ and $l$. We do not know the growth rate in each row of the table. Perhaps it is quadratic; that would be to say that for a fixed $l$, $\eta(k,l)=\Theta(k^2)$. This is indeed true for $l=1$, as proved by Nilli [16].

$k=1$     $k=2$     $k=3$     $k=4$     $k=5$     $k=6$     $k=7$     $k=8$

$l=1$     $4$     $11$     $\textbf{15}$–$22$     $\textbf{17}$–$37$     $\textbf{20}$–$56$     $27$–$79$     $38$–$106$     $51$–$137$

[9]     [Th. <ref>]–[17]     [Co. <ref>]–[17]     [Co. <ref>]–[17]     [11]–[17]     [11]–[17]     [11]–[17]

$l=2$     $3$     $\textbf{8}$     $\textbf{15}$     $\textbf{17}$–$37$     $\textbf{20}$–$56$     $\textbf{24}$–$79$     $\textbf{28}$–$106$     $\textbf{32}$–$137$

[Co. <ref>]     [Th. <ref>]     [Co. <ref>]–[17]     [Co. <ref>]–[17]     [Co. <ref>]–[17]     [Co. <ref>]–[17]     [Co. <ref>]–[17]

$l=3$     $3$     $5$     $\textbf{12}$     $\textbf{16}$     $\textbf{20}$–$56$     $\textbf{24}$–$79$     $\textbf{28}$–$106$     $\textbf{32}$–$137$

[Co. <ref>]     [Th. <ref>]     [Co. <ref>]–[17]      [Co. <ref>]–[17]     [Co. <ref>]–[17]     [Co. <ref>]–[17]

$l=4$     $3$     $5$     $7$     $\textbf{16}$     $\textbf{20}$     $\textbf{24}$–$79$     $\textbf{28}$–$106$     $\textbf{32}$–$137$

[Co. <ref>]     [Th. <ref>]     [Co. <ref>]–[17]     [Co. <ref>]–[17]     [Co. <ref>]–[17]

$l=5$     $3$     $5$     $7$     $9$     $\textbf{20}$     $\textbf{24}$     $\textbf{28}$     $\textbf{32}$–$137$

[Co. <ref>]     [Th. <ref>]     [Th. <ref>]     [Co. <ref>]–[17]

$l=6$     $3$     $5$     $7$     $9$     $11$     $\textbf{24}$     $\textbf{28}$     $\textbf{32}$

[Co. <ref>]     [Th. <ref>]     [Th. <ref>]

$l=7$     $3$     $5$     $7$     $9$     $11$     $13$     $\textbf{28}$     $\textbf{32}$

[Co. <ref>]     [Th. <ref>]

$l=8$     $3$     $5$     $7$     $9$     $11$     $13$     $15$     $\textbf{32}$

[Co. <ref>]

Known values/bounds on the smallest order of a not $C_{2l+1}$-colourable graph of odd-girth $2k+1$. Bold values are proved in this paper.

§ PRELIMINARIES

This section is devoted to introduce some preliminary notions and results that will be useful.

§.§ Circular chromatic number

We recall some basic notions related to circular colourings. For a survey on the matter, consult [24].
Given two integers $p$ and $q$ with $gcd(p,q)=1$, the circular clique $C(p,q)$ is the graph
on vertex set $\{0,\ldots, p-1\}$ with $i$ adjacent to $j$ if and only if $q\leq |i-j|\leq p-q$.
A homomorphism of a graph $G$ to $C(p,q)$ is called a $(p,q)$-colouring, and the circular chromatic number
of $G$, denoted $\chi_c(G)$, is the smallest rational $p/q$ such that $G$ has a $(p,q)$-colouring.
Since $C(p,1)$ is the complete graph $K_{p}$, we have $\chi_c(G)\leq \chi(G)$.
On the other hand $C(2l+1,l)$ is the cycle $C_{2l+1}$. Thus $C_{2l+1}$-colourability is about deciding whether $\chi_c(G)\leq 2+\frac{1}{l}$. It is a well-known fact that $C(p,q)\to C(r,s)$ if and only if $\frac{p}{q} \leq \frac{r}{s}$, in particular we will use the fact that $C(12,5)\to C_5$.

§.§ Odd-$K_4$'s and a theorem of Gerards

The following notion will be central in our proofs. An odd-$K_4$ is a subdivision of the complete graph $K_4$ where each of the four triangles of $K_4$ has become an odd-cycle [6]. Furthermore, we call it a $(2k+1)$-odd-$K_4$ if each such cycle has length exactly $2k+1$.
Since subdivided triangles are the only odd-cycles of an odd-$K_4$, the odd-girth of a $(2k+1)$-odd-$K_4$ is $2k+1$. The following is common knowledge about odd-$K_4$'s, but for the sake of completeness we include a proof.

Let $K$ be an odd-$K_4$ of odd-girth at least $2k+1$. Then, $K$ has order at least $4k$, with equality if and only if $K$ is a $(2k+1)$-odd-$K_4$.
Furthermore, in the latter case any two disjoint edges of $K_4$ are subdivided the same number of times when constructing $K$.

Since $K$ has odd-girth at least $2k+1$, each of the four cycles of $K$ has length at least $2k+1$. Hence, $2|E(K)|\geq 4(2k+1)$. On the other hand, four of the vertices of $K$ (original vertices of $K_4$) are of degree $3$ and all other vertices are of degree $2$. Therefore $|V(K)|=|E(K)|-2$ which implies that $|V(K)|\geq 4k$, and equality holds precisely when each face has length exactly $2k+1$, that is to say $K$ is a $(2k+1)$-odd-$K_4$.
Suppose equality holds and assume that edges of $K_4$ are subdivided into paths of lengths $a$, $a'$, $b$, $b'$, $c$ and $c'$, where each pair $i,i'$ with $i\in\{a,b,c\}$ correspond to disjoint edges of $K_4$. Then, we have $a+b'+c'=a+b+c=2k+1$. Thus, $b'+c'=b+c$. Similarly, $a'+b'=a+b$, and $a'+c'=a+c$. This implies that $a=a'$, $b=b'$ and $c=c'$, as claimed.

A $(2k+1)$-odd-$K_4$ is, more precisely, referred to as an $(a,b,c)$-odd-$K_4$ if three edges of a triangle of $K_4$ are subdivided into paths of length $a$, $b$ and $c$ respectively (by Proposition <ref> this is the case for all four triangles). Note that while terms "odd-$K_4$" or "$(2k+1)$-odd-$K_4$" refer to many non-isomorphic graphs, an $(a,b,c)$-odd-$K_4$ ($a+b+c=2k+1$) is a unique graph up to a relabeling of vertices.

An odd-$K_3^2$ is a graph obtained from three disjoint odd-cycles and three disjoint paths (possibly of length $0$) joining each pair of cycles [6]. Thus, in such a graph, any two of the three cycles have at most one vertex in common (if the path joining them has length $0$). Hence, an odd-$K_3^2$ of odd-girth at least $2k+1$ has order at least $6k$.

If $G$ has neither an odd-$K_4$ nor an odd-$K_3^2$ as a subgraph, then it admits a homomorphism to its shortest odd-cycle.

We have the following corollary of Proposition <ref> and Theorem <ref>.

For any positive integer $k$, we have $\eta(k,k)=4k$.

Consider a graph $G$ of odd-girth $2k+1$ which does not admit a homomorphism to $C_{2k+1}$. It follows from Theorem <ref> that $G$ contains either an odd-$K_4$, or an odd-$K_3^2$. If it contains the latter, then $G$ has at least $6k$ vertices. Otherwise, $G$ must contain an odd-$K_4$ of odd-girth at least $2k+1$, and then by Proposition <ref>, $G$ has at least $4k$ vertices. This shows that $\eta(k,k)\geq 4k$.

Moreover, any $(2k+1)$-odd-$K_4$ has order $4k$ (by Proposition <ref>) and admits no homomorphism to $C_{2k+1}$, showing that $\eta(k,k)\leq 4k$.

Since $C_{2l+3}$ maps to $C_{2l+1}$ and by transitivity of homomorphisms, a graph with no homomorphism to $C_{2l+1}$ also has no homomorphism to $C_{2l+3}$. This implies the following.

Let $k,l$ be two positive integers. We have $\eta(k,l)\geq\eta(k,l+1)$.

We thus obtain the following immediate consequence of Corollary <ref> and Observation <ref>.

For any two integers $k,l$ with $k\geq l\geq 1$, we have $\eta(k,l)\geq 4k$.

§ ROWS OF TABLE <REF>

In this section, we study the behavior of $\eta(k,l)$ when $l$ is a fixed value, that is, the behavior of each row of Table <ref>. Note again that whenever $l\geq k+1$, $\eta(k,l)=2k+1$.

As mentioned before, the first row (i.e. $l=1$) is about determining the smallest order of a $4$-chromatic graph of odd-girth $2k+1$ and we know that $\eta(k,1)=\Theta(k^2)$ [16].

It is not difficult to observe that for $k\geq l$, the function $\eta(k,l)$ is strictly increasing, in fact with a little bit of effort one can even show the following.

For $k\geq l$, we have $\eta(k+1,l)\geq \eta(k,l)+2$.

Let $G$ be a graph of odd-girth $2k+3$ and order $\eta(k+1,l)$ that does not map to $C_{2l+1}$. Consider any $(2k+3)$-cycle $v_0\cdots v_{2k+2}$ of $G$, and build a smaller graph by identifying $v_0$ with $v_2$ and $v_1$ with $v_3$. It is not difficult to check that the resulting graph has odd-girth exactly $2k+1$ and does not map to $C_{2l+1}$ (otherwise, $G$ would), proving the claim.

While  we expect that for a fixed $l$, $\eta(k,l)$ grows quadratically in terms of $k$, we show, somewhat surprisingly, that at least just after the threshold of $k=l$, the function $\eta(k,l)$ only increases by $4$ when $l$ increases by $1$, implying that Proposition <ref> cannot be improved much in this formulation.
More precisely, we have the following theorem.

For any $k,l\geq 3$ and $l\leq k\leq\frac{3l+i-3}{2}$ (where $2k=i\bmod 3$), we have $\eta(k,l)=4k$.

To prove this theorem, we give a family of odd-$K4$'s which are of odd-girth $2k+1$, but do not map to $C_{2l+1}$. This is done in the next theorem, after which we give a proof of Theorem <ref>.

We say that a thread is a path where the internal vertices have degree $2$.

Let $p\geq 3$ be an integer. If $p$ is odd, any $(a,b,c)$-odd-$K_4$ with $(a,b,c)\in\{(p-1,p-1,p),(p,p,p)\}$ has no homomorphism to $C_{2p+1}$. If $p$ is even, any $(p-1,p,p)$-odd-$K_4$ has no homomorphism to $C_{2p+1}$.

Let $(a,b,c)\in \{(p-1,p-1,p),(p,p,p),(p-1,p,p)\}$ and let $K$ be an $(a,b,c)$-odd-$K_4$. Let $t$, $u$, $v$, $w$ be the vertices of degree $3$ in $K$ with the $tu$-thread of length $a$, the $uv$-thread of length $b$ and the $tv$-thread of length $c$. We now distinguish two cases depending on the parity of $p$ and the value of the triple $(a,b,c)$.

Case 1. Assume that $p$ is odd and $(a,b,c)\in\{(p-1,p-1,p),(p,p,p)\}$. By contradiction, we assume that there is a homomorphism $h$ of $K$ to $C_{2p+1}$. Then, the cycle $C_{tvw}$ formed by the union of the $tv$-thread, the $vw$-thread and the $tw$-thread is an odd-cycle of length $a+b+c$. Therefore, its mapping by $h$ to $C_{2p+1}$ must be onto. Thus, $u$ has the same image by $h$ as some vertex $u'$ of $C_{tvw}$.
Note that $u'$ is not one of $t$, $v$ or $w$, indeed by identifying $u$ with any of these vertices we obtain a graph containing an odd-cycle of length $p$ or $2p-1$; thus, this identification cannot be extended to a homomorphism to $C_{2p+1}$. Therefore, $u'$ is an internal vertex of one of the three maximal threads in $C_{tvw}$. Let $C_u$ be the odd-cycle of length $a+b+c$ containing $u$ and $u'$. After identifying $u$ and $u'$, $C_u$ is transformed into two cycles, one of them being odd. If $(a,b,c)=(p,p,p)$, then $C_{u}$ has length $3p$. Then, the two newly created cycles have length at least $p+1$, and thus at most $2p-1$. If $(a,b,c)=(p-1,p-1,p)$, then $C_{u}$ has length $3p-2$, and the two cycles have length at least $p$ and at most $2p-2$. In both cases, we have created an odd-cycle of length at most $2p-1$. Hence, this identification cannot be extended to a homomorphism to $C_{2p+1}$, a contradiction.

Case 2. Assume that $p$ is even and $(a,b,c)=(p-1,p,p)$, and that $h$ is a homomorphism of $K$ to $C_{2p+1}$. Again, the image of $C_{tvw}$ by $h$ is onto, and $u$ has the same image by $h$ as some vertex $u'$ of $C_{tvw}$. If $u'=t$, identifying $u$ and $u'$ produces an odd $(p-1)$-cycle, a contradiction. If $u'\in\{v,w\}$, then we obtain a $(2p-1$)-cycle, a contradiction as well. Therefore, $u'$ is an internal vertex of one of the three maximal threads in $C_{tvw}$. Let $C_u$ be the odd-cycle of length $3p-1$ containing $u$ and $u'$. As in Case $1$, after identifying $u$ and $u'$, $C_{u}$ is transformed into two cycles, each of length at least $p$ and at most $2p-1$. One of them is odd, a contradiction again.

We note that Theorem <ref> is tight, in the sense that if $p$ is odd and $(a,b,c)\in\{(p-1,p-1,p),(p,p,p)\}$ or if $p$ is even and $(a,b,c)=(p-1,p,p)$, any $(a,b,c)$-odd-$K_4$ has a homomorphism to $C_{2p-1}$.

We can now prove Theorem <ref>.

By Corollary <ref>, we know that $\eta(k,l)\geq 4k$.
We now prove the upper bound. Recall that $\eta(k,l)\leq\eta(k,l-1)$. If $2k=0\bmod 3$, then $p=\frac{2k+3}{3}$ is an odd integer, and $p\leq l$. By Theorem <ref>, a $(p-1,p-1,p)$-odd-$K_4$, which has order $6p-6=4k$, has no homomorphism to $C_{2p+1}$, and thus $\eta(k,l)\leq\eta(k,p)\leq 4k$. Similarly, if $2k=1\bmod 3$, then $p=\frac{2k+2}{3}$ is an even integer, and $p\leq l$. By Theorem <ref>, a $(p-1,p,p)$-odd-$K_4$, which has order $6p-4=4k$, has no homomorphism to $C_{2p+1}$, and thus $\eta(k,l)\leq\eta(k,p)\leq 4k$. Finally, if $2k=2\bmod 3$, then $p=\frac{2k+1}{3}$ is an odd integer, and $p\leq l$. By Theorem <ref>, a $(p,p,p)$-odd-$K_4$, which has order $6p-2=4k$, has no homomorphism to $C_{2p+1}$, and thus $\eta(k,l)\leq\eta(k,p)\leq 4k$.

§ THE VALUE OF $\ETA(3,2)$

We now determine $\eta(3,2)$, which is not covered by Theorem <ref>. By Corollary <ref>, we know that $\eta(3,2)\geq 12$. In fact, we will show that $\eta(3,2)=15$. Using a computer search, Gordon Royle (private communication, 2016) has found that there are at least ten graphs of order $15$ and odd-girth $7$ that do not admit a homomorphism to $C_5$. For example, see the three graphs of Figure <ref>. Thus, $\eta(3,2)\leq 15$. Next, we prove that this upper bound is tight.

[]0.7[join=bevel,inner sep=0.5mm,scale=0.7]

[draw,shape=circle,fill](u0) at (0:3) ;

[draw,shape=circle,fill](u1) at (60:3) ;

[draw,shape=circle,fill](u2) at (120:3) ;

[draw,shape=circle,fill](u3) at (180:3) ;

[draw,shape=circle,fill](u4) at (240:3) ;

[draw,shape=circle,fill](u5) at (300:3) ;

[draw,shape=circle,fill](v0) at (0:1.75) ;

[draw,shape=circle,fill](v1) at (60:1.75) ;

[draw,shape=circle,fill](v2) at (120:1.75) ;

[draw,shape=circle,fill](v3) at (180:1.75) ;

[draw,shape=circle,fill](v4) at (240:1.75) ;

[draw,shape=circle,fill](v5) at (300:1.75) ;

[draw,shape=circle,fill](w0) at (30:0.75) ;

[draw,shape=circle,fill](w1) at (150:0.75) ;

[draw,shape=circle,fill](w2) at (270:0.75) ;

[line width=1pt] (u0)–(u1)–(u2)–(u3)–(u4)–(u5)–(u0)–(v0)–(v1)–(w1)–(v4)–(v5)–(w0)–(v2)–(v3)–(w2)–(v0) (u1)–(v1) (u2)–(v2) (u3)–(v3) (u4)–(v4) (u5)–(v5);

[]0.7[join=bevel,inner sep=0.5mm,scale=0.7]

[draw,shape=circle,fill](u0) at (0:3) ;

[draw,shape=circle,fill](u1) at (45:3) ;

[draw,shape=circle,fill](u2) at (90:3) ;

[draw,shape=circle,fill](u3) at (135:3) ;

[draw,shape=circle,fill](u4) at (180:3) ;

[draw,shape=circle,fill](u5) at (225:3) ;

[draw,shape=circle,fill](u6) at (270:3) ;

[draw,shape=circle,fill](u7) at (315:3) ;

[draw,shape=circle,fill](v0) at (-12:1.5) ;

[draw,shape=circle,fill](v1) at (60:1.5) ;

[draw,shape=circle,fill](v2) at (120:1.5) ;

[draw,shape=circle,fill](v3) at (192:1.5) ;

[draw,shape=circle,fill](v4) at (240:1.5) ;

[draw,shape=circle,fill](v5) at (300:1.5) ;

[draw,shape=circle,fill](v6) at (270:2.2) ;

[line width=1pt] (u0)–(u1)–(u2)–(u3)–(u4)–(u5)–(u6)–(u7)–(u0)–(v0)–(v1)–(u1) (u3)–(v2)–(v3)–(u4) (u5)–(v4)–(v6)–(v5)–(u7) (u6)–(v6) (v0)–(v3) (v1)–(v4) (v2)–(v5);
[]0.7[join=bevel,inner sep=0.5mm,scale=0.7]

[draw,shape=circle,fill](u0) at (347.2:3) ;

[draw,shape=circle,fill](u1) at (38.6:3) ;

[draw,shape=circle,fill](u2) at (90:3) ;

[draw,shape=circle,fill](u3) at (140.4:3) ;

[draw,shape=circle,fill](u4) at (192.8:3) ;

[draw,shape=circle,fill](u5) at (245.2:3) ;

[draw,shape=circle,fill](u6) at (295.6:3) ;

[draw,shape=circle,fill](v0) at (347.2:1.8) ;

[draw,shape=circle,fill](v2) at (90:1.7) ;

[draw,shape=circle,fill](v4) at (192.8:1.8) ;

[draw,shape=circle,fill](v5) at (245.2:1.8) ;

[draw,shape=circle,fill](v6) at (295.6:1.8) ;

[draw,shape=circle,fill](w0) at (0,-0.4) ;
[draw,shape=circle,fill](w1) at (38.6:1) ;
[draw,shape=circle,fill](w3) at (140.4:1) ;

[line width=1pt] (u0)–(u1)–(u2)–(u3)–(u4)–(u5)–(u6)–(u0)
(v0)–(w0) (w1)–(v6) (v5)–(w3) (v4)–(w0);

Three graphs of order $15$ and odd-girth $7$ with no homomorphism to $C_5$.

Any graph $G$ of order at most $14$ and odd-girth at least $7$ admits a homomorphism to $C_5$, and thus $\eta(3,2)=15$.

We consider a $C_5$ on the vertex set $\{0,1,2,3,4\}$  where vertex $i$ is adjacent to vertices $i+1$ and $i-1$ (modulo $5$). Thus, in the following, to give a $C_5$-colouring
we will give a colouring using element of $\{0,1,2,3,4\}$ where adjacent pairs are mapped into (cyclically) consecutive elements of this set.

Given a graph $G$ and a vertex $v$ of it, we partition $V(G)$ into four sets
$\{v\}, N_1(v), N_2(v)$ and $\N3(v)$ where $N_1(v)$ (respectively $N_2(v)$)
designates the set of vertices at distance exactly 1 (respectively 2) of $v$,
and $\N3(v)$ the vertices at distance 3 or more of $v$. A proper 3-colouring of $G[\N3(v)]$ using colours $c_1, c_2$	and $c_3$ is said to be $v$-special if:

(i) each vertex with colour $c_3$ is an isolated vertex of $G[\N3(v)]$,

(ii) no vertex from $N_2(v)$ sees both colours $c_1$ and $c_2$.

A key observation is the following: given any graph $G$, if for some
vertex $v$ of $G$, there exists a $v$-special colouring of $G[\N3(v)]$,
then $G$ maps to $C_5$. Such a homomorphism is given by
mapping $c_1$-vertices to 0, $c_2$-vertices to 1 and $c_3$-vertices
to 3, and then extending as follows:

* for any vertex $u$ in $N_2(v)$, if $u$ has a $c_1$-neighbour,
map it to 4; otherwise, map it to 2,

* all vertices of $N_1(v)$ are mapped to 3,

* vertex $v$ is mapped to 2 or 4.

Now, let $G$ be a minimal counterexample to the claim of Theorem <ref>. We
first collect a few properties of $G$. The previous paragraph allows
us to state our first claim.

For no vertex $v$ of $G$ there is a $v$-special colouring of $G[\N3(v)]$.

Since $G$ is a minimal counterexample, it cannot map to a subgraph of
itself (which would be a smaller counterexample). Thus, we may assert
our second claim.

Graph $G$ is a core.

In particular, we also have the following claim.

For any two vertices $u$ and $v$ of $G$, $N(u) \not\subseteq N(v)$.

Recall that a walk between two vertices $u$ and $v$ is a sequence of (not necessarily distinct) vertices starting with $u$ and ending with $v$, where two consecutve vertices in the sequence are adjacent. A walk betseen $u$ and $v$ is an $uv$-walk, and a $k$-walk is a walk with $k+1$ vertices.

For any two distinct vertices $u$ and $v$ of $G$, there is a $uv$-walk of length 5.

Otherwise, identifying $u$ and $v$ would result in a
strictly smaller graph of yet odd-girth 7 which does not map to $C_5$,
contradicting the minimality of $G$.

Graph $G$ has no thread of length 4 or more.

Once again, by minimality of $G$, if we remove such a
thread of length 4, the resulting graph can be mapped to $C_5$. But
since there is a walk of length 4 between any two vertices of $C_5$,
this mapping could easily be extended to $G$.Now we can state a more difficult claim.

There is no vertex of $G$ of degree 4 or more, nor a vertex of degree exactly 3 with
a second neighbourhood of size 5 or more.

For a contradiction, suppose that a vertex $v$ has degree 4 or
more, or has degree 3 and a second neighbourhood of size 5 or more.

By Claim <ref>, the neighbours of $v$ should have
pairwise distinct neighbourhoods, so that even if $v$ has degree $4$ or
more, we must have $|N_2(v)| \geq 4$. Thus, by a counting argument
(recall that $G$ has at most 14 vertices), we may state that
$\N3(v)$ has size at most 5. Since $G$ has odd-girth 7, it means that
$G[\N3(v)]$ is bipartite.

Suppose $G[\N3(v)]$ has only one non-trivial connected
component. Consider any proper $3$-colouring of $G[\N3(v)]$ such that
colours $c_1$ and $c_2$ are used for the non-trivial connected
component, and colour $c_3$ is used for isolated vertices. Then, no
vertex of $N_2(v)$ can see both colours $c_1$ and $c_2$, as this would
result in a short odd-cycle in $G$. Thus, any such colouring is
$v$-special. Such a colouring clearly exists, hence by
Claim <ref>, we derive that $G[\N3(v)]$ has at least two
non-trivial components. Since it has order at most 5, it must have
exactly two non-trivial components.

Assume now that both non-trivial connected components are isomorphic
to $K_2$. Consider all proper $3$-colourings of $G[\N3(v)]$ such that
colours $c_1$ and $c_2$ are used for the copies of $K_2$ (the
potentially remaining vertex being coloured with $c_3$). One may check
that since by Claim <ref>, none of them is $v$-special, and hence there is a short odd-cycle in
$G$, which is a contradiction.

Hence, $G[\N3(v)]$ is isomorphic to the disjoint union of
$K_2$ and $K_{2,1}$. Let $u_1$ and $u_2$ be the vertices of
$K_2$, and $u_3, u_4$ and $u_5$ be the vertices of $K_{2,1}$
such that $u_4$ is the central vertex.

Let $\vphi_1$ and $\vphi_2$ be two proper 2-colourings of $G[\N3(v)]$
as follows: $\vphi_1(u_1) = \vphi_1(u_3) = \vphi_1(u_5) = c_1$ and
$\vphi_1(u_2) = \vphi_1(u_4) = c_2$, $\vphi_2(u_2) = \vphi_2(u_3) =
\vphi_2(u_5) = c_1$ and $\vphi_2(u_1) = \vphi_2(u_4) = c_2$. Since
$\vphi_1$ is not $v$-special, there is either a vertex $t_1$ adjacent
to $u_2$ and $u_3$ (by considering the symmetry of $u_3$ and $u_5$), or a
vertex $t_1'$ adjacent to $u_1$ and $u_4$. Similarly, since $\vphi_2$
is not $v$-special, either there is a vertex $t_2$ adjacent to $u_1$
and one to $u_3$ and $u_5$, or there is a vertex $t_2'$ adjacent to
$u_2$ and $u_4$. The existence of some $t_i'$ (for $i = 1$ or $2$),
together with any of these three remaining vertices would result in a
short odd-cycle in $G$. Thus, the only option is for $t_1$ and $t_2$
to exist and more precisely, $t_2$ has to be a neighbour of $u_5$.

Next, we show that $u_4$ has degree at least 3. Suppose not,
then it has degree exactly 2. Let $\vphi_3$ be a partial
$C_5$-colouring of $G$ defined as follows: $\vphi_3(u_1) =
\vphi_3(u_5) = 0, \vphi_3(u_2) = 1, \vphi_3(u_3) = 3$ and
$\vphi_3(u_4) = 4$. Then, no vertex in $N_2(v)$ sees both 0
and 1 (by odd-girth arguments). Thus, we can extend $\vphi_3$
to $N_2(v)$ using only colours 2 and 4 on these
vertices. Then, all vertices of $N_1(v)$ can be mapped to 3
and $v$ can be mapped to 2, which contradicts the fact that
$G$ is a counterexample.

Hence, there exists a vertex $t_3$ in $N_2(v)$ which is
adjacent to $u_4$. Note that, by the odd-girth condition,
$t_3$ has no other neighbour in $G[\N3(v)]$ and, in
particular, it must be distinct from $t_1$ and $t_2$. Vertices
$t_1, t_2$ and $t_3$ are in $N_2(v)$, so there are vertices
$s_1$, $s_2$ and $s_3$ in $N_1(v)$ such that $s_i$ is adjacent
to $t_i$ for $i$ between 1 and 3. Moreover, vertices $t_1,
t_2$ and $t_3$ are pairwise connected by a path of
length 3. Therefore, their neighbourhoods cannot intersect, so
that vertices $s_1, s_2$ and $s_3$ are distinct.

Now, consider the partial $C_5$-colouring $\vphi_3$ again. We may
extend $\vphi_3$ to $N_2(v)$ by assigning colour 0 to neighbours of
$u_4$, colour 4 to neighbours of $u_1$ and $u_5$, and colour 2 to the
rest. If no vertex of $N_1(v)$ sees both colours 0 and 4 in $N_2(v)$,
we may colour $N_1(v)$ with 1 and 3 and colour $v$ with 2, which is a
contradiction. Thus, there exists some vertex $x$ in $N_1(v)$ seeing
both colours 0 and 4 in $N_2(v)$. The only vertices with colour 0 in
$N_2(v)$ are neighbours of $u_4$ so that $x$ must be at distance 2
from $u_4$. Since there is no short odd-cycle in $G$, vertex $x$
cannot be at distance 2 from $u_5$. Thus, it is at distance 2 from
$u_1$. Let $t_4$ be the middle vertex of this path from $x$ to
$u_1$. Now $t_4$ is a neighbour of $u_1$ which is distinct from $t_1,
t_2$ and $t_3$. By the symmetry between $u_1$ and $u_2$, there must be a
fifth vertex $t_5$ in $N_2(v)$ which is a neighbour of $u_2$ and
distinct from $t_1,t_2,t_3$ and $t_4$. Moreover, $t_5$ has a neighbour
$y$ in $N_1(v)$ that is at distance 2 from $u_4$. We can readily check
that $y$ is distinct from $x, s_1$ and $s_2$. Thus, $N_1(v)$ has size
at least 4 and $N_2(v)$ has size at least 5, which is a contradiction
with the order of $G$ (which should be at most 14). This concludes the
proof of Claim <ref>.

$G$ contains no $6$-cycle.

Suppose, by contradiction, that $G$ contains a $6$-cycle $C:v_0,\ldots, v_{5}$. For a pair $v_i$ and $v_{i+2}$ (addition in indices are done modulo $6$) of vertices of $C$, the $5$-walk connecting them (see Claim <ref>) is necessarily a $5$-path, which we denote by $P^i$. Furthermore, at most one inner-vertex of $P^i$ may belong to $C$, and if it does, it must be a neighbour of $v_i$ or $v_{i+2}$ (one can check that otherwise, there is a short odd-cycle in $G$).

Assume first that none of the six paths $P^i$ ($0\leq i\leq 5$) has any inner-vertex on $C$. In this case and by Claim <ref>, we observe that the neighbours of $v_i$ in $P^i$ and $P^{i+4}$ (additions in superscript are modulo $6$) are the same. Let $v_i'$ be this neighbour of $v_i$.

Vertices $v'_i$ , $i=0,1, \ldots, 5$ are all distinct, as otherwise we have a short odd-cycle in $G$. Let $x$ and $y$ by two internal vertices of $P^1$
distinct from  $v'_0$ and $v'_2$. By our assumption, $x$ and $y$ are distinct from vertices of $C$. We claim that they are also distinct from $v_i'$, $i=0, \ldots, 5$. Vertex $x$ is indeed distinct from $v_0'$ and $v_2'$ by the choice of $P^0$. It is distinct from $v_1',v_3'$ and $v_4'$ as otherwise there will be a short odd-cycle. Similarly, $y$ is distinct from $v_0', v_1', v_2', v_4', v_5'$. For the same reason, we cannot simultaneously have $x=v_5'$ and $y=v_3'$. Finally, if we have $x=v_5'$ then $\{v_0', v_1, y, v_3, v_4'\}\subseteq N_2(x)$ and $d(x)\geq 3$, contradicting Claim <ref>.
As a result, since $|V(G)|\leq 14$, $x$ and $y$ are internal vertices of all $P^i$'s. But then it easy to find a short odd-cycle.

Hence, we may assume, without loss of generality, that $P^1$ has one inner-vertex on $C$, say $v'_1=v_0$. Let $v_0x_1x_2x_3v_3$ be the $4$-path connecting $v_0$ and $v_3$ (recall that $x_i\notin C$ for $i=1,2,3$). We next assume that $P^5$ does not have any inner-vertex in $C$. Then, no vertex of $P^5$ is a vertex from $\{x_1,x_2,x_3\}$, for otherwise we have a short odd-cycle in $G$. But then, $v_0$ violates Claim <ref>. Therefore, an inner-vertex of $P^5$ lies on $C$, say it is $v_2$ and we have $P^5:v_5y_1y_2y_3v_2v_1$. Then, $P^1$ and $P^5$ are vertex-disjoint, for otherwise we have a short odd-cycle in $G$. Remark that $C$ together with the union of the paths $P^i$, $i=0,\ldots, 5$, forms a $(2k+1)$-odd $K_4$, in fact it is a $(1,2,4)$-odd-$K_4$ (a subgraph of $C(12,5)$). Now, because of the odd-girth of $G$, and by Claim <ref>, the only third neighbour of $v_1$, if any, is $v_4$ (and vice-versa). Furthermore, the set $\{x_1,x_2,x_3,y_1,y_2,y_3\}$ of vertices induces a subgraph matching the $x_iy_i$ with $i=1,2,3$. If there is no additional vertex in $G$, then $G$ has order $12$ and it is a subgraph of $C(12,5)$. But then, the circular chromatic number of $G$ is at most $12/5$, which implies that $G$ has a homomorphism to $C_5$, a contradiction. Thus, $G$ has order at least $13$. Again by Claim <ref>, any of the two last potentially existing vertices of $G$ can be adjacent only to $x_2$ or $y_2$. Without loss of generality (considering the symmetries of the graph), assume that $x_2$ has an additional neighbour, $v$. Then, either $v$ is also adjacent to $y_2$ (then $G$ has order $13$), or $v$ and $y_2$ have a common neighbour, say $w$. If $v$ is adjacent to both $x_2$ and $y_2$, then one can check that there is no edge in the set $\{x_1,x_2,x_3,y_1,y_2,y_3\}$ (otherwise we have a short odd-cycle). But then, we exhibit a homomorphism of $G$ to $C_5$: map $x_3$, $y_1$, $v$ to $0$; $x_2$, $y_2$ to $1$; $v_1$, $x_1$, $y_3$ to $2$; $v_0$, $v_2$, $v_4$ to $3$; $v_3$ and $v_5$ to $4$. This is a contradiction. Thus, $v$ and $y_2$ have a common neighbour $w$, and both $v$ and $w$ are of degree $2$. We now create a homomorphic image of $G$ by identifying $v$ with $y_2$ and $w$ with $x_2$. Then, this homomorphic image of $G$ is a subgraph of $C(12,5)$, and thus the circular chromatic number of $G$ is at most $12/5$, which implies that $G$ has a homomorphism to $C_5$, a contradiction. This completes the proof of Claim <ref>.

$G$ contains no $4$-cycle.

Assume by contradiction that $G$ contains a $4$-cycle $C:tuvw$. As in the proof of Claim <ref>, there must be two $5$-paths $P_{tv}:ta_1a_2a_3a_4v$ and $P_{uw}:ub_1b_2b_3b_4w$ connecting $t$ with $v$ and $u$ with $w$, respectively. Moreover, these two paths must be vertex-disjoint because of the odd-girth of $G$. Thus, the union of $C$, $P_{tv}$ and $P_{uw}$ forms a $(1,1,5)$-odd-$K_4$, $K$. By assumption on the odd-girth of $G$, any additional edge inside $V(K)$ must connect an internal vertex of $P{tv}$ to an internal vertex of $P_{uw}$. But any such edge would either create a short odd-cycle or a $6$-cycle in $G$, the latter contradicting Claim <ref>. Thus, the only edges in $V(K)$ are those of $K$. If there is no additional vertex in $G$, we have two $5$-threads in $G$, contradicting Claim <ref>; hence there is at least one additional vertex in $G$, say $x$, and perhaps a last vertex, $y$. Note that $t$, $u$, $v$ and $w$ are already, in $K$, degree $3$-vertices with a second neighbourhood of size $4$, thus by Claim <ref> none of $t$, $u$, $v$, $w$, $a_1$, $a_4$, $b_1$ and $b_4$ are adjacent to any vertex not in $K$. Thus $N(x), N(y) \subseteq \{a_2, a_3, b_2, b_3, x, y\}$.

Assume that some vertex not in $K$ (say $x$) is adjacent to two vertices of $K$. Then, these two vertices must be a vertex on the $tu$-path of $K$ ($a_2$ or $a_3$, without loss of generality it is $a_2$) and a vertex on the $vw$-path of $K$ ($b_2$ or $b_3$). By the automorphism of $K$ that consists of swapping $v$ and $w$ and reversing the $vw$-path, without loss of generality we can assume that the second neighbour of $x$ in $K$ is $b_3$. Then, we claim that $G$ has no further vertex. Indeed, if there is a last vertex $y$, since $a_2$ and $b_3$ have already got three neighbours, $y$ must be adjacent to at least two vertices among $\{a_3,b_2,x\}$. If it is adjacent to both $a_3$ and $b_2$, we have a $6$-cycle, contradicting Claim <ref>; otherwise, $y$ is of degree $2$ but part of a $4$-cycle, implying that $G$ is not a core, a contradiction again. Thus, $G$ has order $13$ and no further edge. We create a homomorphic image of $G$ by identifying $x$ and $a_3$. The obtained graph is a subgraph of $C(12,5)$. Hence, $G$ has circular chromatic number at most $12/5$ and has a homomorphism to $C_5$, a contradiction.

Thus, any vertex not in $K$ has at most one neighbour in $K$. Since $G$ has no $4$-thread, one vertex not in $K$ (say $x$) is adjacent to one of $a_2$ or $a_3$ (without loss of generality, say $a_2$), and the last vertex, $y$, is adjacent to one of $b_2$ and $b_3$ (as before, by the symmetries of $K$ we can assume it is $b_2$). Moreover, $x$ and $y$ must be adjacent, otherwise they both have degree $1$. Also there is no further edge in $G$. But then, as before, we create a homomorphic image of $G$ by identifying $x$ with $b_2$ and $y$ with $a_2$. The resulting graph is a subgraph of $C(12,5)$, which again gives a contradiction. This completes the proof of Claim <ref>.

To complete the proof, we note that since $G$ has no homomorphism to $C_5$, it also has no homomorphism to $C_7$. Thus, by Theorem <ref>, $G$ must contain either an odd-$K_3^2$ or an odd-$K_4$ of odd-girth at least $7$. Since such an odd-$K_3^2$ must have at least $18$ vertices, $G$ contains an odd-$K_4$. Let $H$ be such an odd-$K_4$ of $G$. Since its girth is at least $7$, by Proposition <ref> it has at least $12$ vertices. We consider three cases, depending on the order of $H$.

Case 1. Assume that $|V(H)|=12$. By Proposition <ref>, $H$ is a $(2k+1)$-odd-$K_4$, in fact, it is an $(a,b,c)$-odd-$K_4$ with $a+b+c=7$. Since $H$ has girth at least $7$, we have only two possibilities: (i) $(a,b,c)=(2,2,3)$ or (ii) $(a,b,c)=(1,3,3)$.
Each of these two possible odd-$K_4$'s is of diameter $4$. Furthermore, in each case, the pairs at distance $4$ are isomorphic (each pair consists of two internal vertices of two disjoint threads of length $3$).
If $G$ contains one more vertex that $H$, say $x$, then either $x$ is of degree at most 1, which contradicts Claim <ref> or it creates a cycle of length at most 6. Thus $G$ has exactly two more vertices, say $x$ and $y$ and each of them is adjacent to at most one vertex in $H$. These two neighbours of $x$ and $y$ are at distance 4 in $H$ and $x$ is adjacent to $y$.
There are only two non-isomorphic such possibilities.  A homomorphism to $C_5$ in each of these two possibilities is given in Figure <ref>.

[$(a,b,c)=(2,2,3)$]0.6[join=bevel,inner sep=0.6mm]

[draw,shape=circle,fill] (x) at (0,0) ;
(x) node[left=0.2cm] $2$;
[draw,shape=circle,fill] (y) at (6,0) ;
(y) node[right=0.2cm] $0$;
[draw,shape=circle,fill] (z) at (3,5.2) ;
(z) node[above=0.2cm] $2$;
[draw,shape=circle,fill] (t) at (3,1.7) ;
(t) node[above right=0.1cm] $0$;

[draw,shape=circle,fill] (a1) at (3,3.4) ;
(a1) node[left=0.2cm] $1$;

[draw,shape=circle,fill] (ap1) at (3,0) ;
(ap1) node[above=0.2cm] $1$;

[draw,shape=circle,fill] (b1) at (1.5,2.6) ;
(b1) node[left=0.2cm] $3$;

[draw,shape=circle,fill] (bp1) at (4.5,0.85) ;
(bp1) node[above=0.2cm] $1$;

[draw,shape=circle,fill] (c1) at (1,0.57) ;
(c1) node[above=0.2cm] $3$;
[draw,shape=circle,fill] (c2) at (2,1.13) ;
(c2) node[above=0.2cm] $4$;

[draw,shape=circle,fill] (cp1) at (4,3.5) ;
(cp1) node[right=0.2cm] $3$;
[draw,shape=circle,fill] (cp2) at (5,1.75) ;
(cp2) node[right=0.2cm] $4$;

[draw,shape=circle,fill] (d1) at (1.5,-1) ;
(d1) node[left=0.2cm] $4$;
[draw,shape=circle,fill] (d2) at (4.5,-1) ;
(d2) node[right=0.2cm] $3$;

[-,line width=0.4mm] (x)–(y)–(z)–(x)–(t)–(y)  (t)–(z) (c1)–(d1)–(d2)–(cp2);
[$(a,b,c)=(1,3,3)$]0.6[join=bevel,inner sep=0.6mm]

[draw,shape=circle,fill] (x) at (0,0) ;
(x) node[left=0.2cm] $0$;
[draw,shape=circle,fill] (y) at (6,0) ;
(y) node[right=0.2cm] $4$;
[draw,shape=circle,fill] (z) at (3,5.2) ;
(z) node[above=0.2cm] $2$;
[draw,shape=circle,fill] (t) at (3,1.7) ;
(t) node[above right=0.1cm] $3$;

[draw,shape=circle,fill] (b1) at (1,1.7) ;
(b1) node[left=0.2cm] $4$;
[draw,shape=circle,fill] (b2) at (2,3.45) ;
(b2) node[left=0.2cm] $3$;

[draw,shape=circle,fill] (bp1) at (4,1.13) ;
(bp1) node[above=0.2cm] $2$;
[draw,shape=circle,fill] (bp2) at (5,0.57) ;
(bp2) node[above=0.2cm] $3$;

[draw,shape=circle,fill] (c1) at (1,0.57) ;
(c1) node[above=0.2cm] $1$;
[draw,shape=circle,fill] (c2) at (2,1.13) ;
(c2) node[above=0.2cm] $2$;

[draw,shape=circle,fill] (cp1) at (4,3.5) ;
(cp1) node[right=0.2cm] $1$;
[draw,shape=circle,fill] (cp2) at (5,1.75) ;
(cp2) node[right=0.2cm] $0$;

[draw,shape=circle,fill] (d1) at (2.5,-1) ;
(d1) node[left=0.2cm] $3$;
[draw,shape=circle,fill] (d2) at (4.25,-1) ;
(d2) node[right=0.2cm] $4$;

[-,line width=0.4mm] (x)–(y)–(z)–(x)–(t)–(y)  (t)–(z) (c2)–(d1)–(d2)–(cp2);
The two graphs considered in Case $1$.

Case 2. Assume that $|V(H)|=13$. Let the lengths of the four odd-cycles of $H$ be $l_1$, $l_2$, $l_3$ and $l_4$. Using the fact that $l_1+l_2+l_3+l_4=2|E(H)|=30$ we conclude that three of these cycles are of length $7$ and the last one is of length $9$. Let $a$, $b$ and $c$ be the lengths of the three maximal threads of $H$ whose union forms the $9$-cycle. Let $a'$, $b'$ and $c'$ be the respective lengths of the corresponding pairwise disjoint threads.
Then, we have $a'+b'+c=7$ and $a+b+c=9$, which implies that $a'+b'=a+b-2$. Together with the similar equalities $a'+c'=a+c-2$ and $b'+c'=b+c-2$, we obtain that $a=a'+1$, $b=b'+1$ and $c=c'+1$. By the symmetries, we may assume that $a\leq b \leq c$. Considering that there are cycles of lengths $2a'+2b'+2$, $2a'+2c'+2$ and $2b'+2c'+2$ in $H$, we have either (i) $a'=b'=c'=2$ or (ii) $a'=1$, $b'=2$ and $c'=3$. In the first case, the graph is of diameter $4$ and thus there is no room for a $14$th vertex; in the second case, there is a unique pair at distance $5$, which leads us to a unique graph on $14$ vertices, by connecting a $14$th vertex to these two diametral vertices. Homomorphisms to $C_5$ for each of these graphs are given in Figure <ref>.

[$(a',b',c')=(2,2,2)$]0.6[join=bevel,inner sep=0.6mm]

[draw,shape=circle,fill] (x) at (0,0) ;
(x) node[left=0.2cm] $0$;
[draw,shape=circle,fill] (y) at (6,0) ;
(y) node[right=0.2cm] $3$;
[draw,shape=circle,fill] (z) at (3,5.2) ;
(z) node[above=0.2cm] $1$;
[draw,shape=circle,fill] (t) at (3,1.7) ;
(t) node[above right=0.1cm] $3$;

[draw,shape=circle,fill] (a1) at (3,4) ;
(a1) node[left=0.2cm] $0$;
[draw,shape=circle,fill] (a2) at (3,2.9) ;
(a2) node[left=0.2cm] $4$;

[draw,shape=circle,fill] (ap1) at (3,0) ;
(ap1) node[above=0.2cm] $4$;

[draw,shape=circle,fill] (b1) at (1,1.7) ;
(b1) node[left=0.2cm] $1$;
[draw,shape=circle,fill] (b2) at (2,3.45) ;
(b2) node[left=0.2cm] $0$;

[draw,shape=circle,fill] (bp1) at (4.5,0.85) ;
(bp1) node[above=0.2cm] $2$;

[draw,shape=circle,fill] (c1) at (1,0.57) ;
(c1) node[above=0.2cm] $1$;
[draw,shape=circle,fill] (c2) at (2,1.13) ;
(c2) node[above=0.2cm] $2$;

[draw,shape=circle,fill] (cp1) at (4.5,2.6) ;
(cp1) node[right=0.2cm] $2$;

[-,line width=0.4mm] (x)–(y)–(z)–(x)–(t)–(y)  (t)–(z);
[$(a',b',c')=(1,2,3)$]0.6[join=bevel,inner sep=0.6mm]

[draw,shape=circle,fill] (x) at (0,0) ;
(x) node[left=0.2cm] $1$;
[draw,shape=circle,fill] (y) at (6,0) ;
(y) node[right=0.2cm] $0$;
[draw,shape=circle,fill] (z) at (3,5.2) ;
(z) node[above=0.2cm] $2$;
[draw,shape=circle,fill] (t) at (3,1.7) ;
(t) node[above right=0.1cm] $0$;

[draw,shape=circle,fill] (a1) at (3,3.4) ;
(a1) node[left=0.2cm] $1$;

[draw,shape=circle,fill] (b1) at (1,1.7) ;
(b1) node[left=0.2cm] $2$;
[draw,shape=circle,fill] (b2) at (2,3.45) ;
(b2) node[left=0.2cm] $1$;

[draw,shape=circle,fill] (bp1) at (4.5,0.85) ;
(bp1) node[above=0.2cm] $1$;

[draw,shape=circle,fill] (c1) at (0.75,0.425) ;
(c1) node[above=0.2cm] $2$;
[draw,shape=circle,fill] (c2) at (1.5,0.85) ;
(c2) node[below=0.2cm] $3$;
[draw,shape=circle,fill] (c3) at (2.25,1.275) ;
(c3) node[above=0.2cm] $4$;

[draw,shape=circle,fill] (cp1) at (4,3.5) ;
(cp1) node[right=0.2cm] $3$;
[draw,shape=circle,fill] (cp2) at (5,1.75) ;
(cp2) node[right=0.2cm] $4$;

[draw,shape=circle,fill] (d) at (0.75,4.5) ;
(d) node[above=0.2cm] $2$;

[-,line width=0.4mm] (x)–(y)–(z)–(x)–(t)–(y)  (t)–(z) (c2)–(d)–(cp1);
The two graphs considered in Case $2$.

Case 3. Assume that $|V(H)|=14$. Again, let $l_1$, $l_2$, $l_3$ and $l_4$ be the lengths of the four odd-cycles of $H$. Then, we have $l_1+l_2+l_3+l_4=2|E(H)|=32$, and either $l_1=l_2=l_3=7$ and $l_4=11$, or $l_1=l_2=7$ and $l_3=l_4=9$. We define $a$, $b$, $c$, $a'$, $b'$ and $c'$ similarly as in Case $2$.
It is then implied that $a=a'+2$, $b=b'+2$ and $c=c'+2$. Since $a',b', c'\geq 1$ we have $a,b,c, \geq 3$ and since $a+b+c=11$ we have two possibilities: either $a=b=3$, $c=5$ or $a=3$, $b=c=4$. In the case $(a,b,c)=(3,3,5)$, the vertex of degree 3 of $H$ which is not on the face of size 11 has already five distinct vertices at distance 2, contradicting Claim <ref>. In the case $(a,b,c)=(3,4,4)$, $H$ is already of diameter $5$, thus $H$ is the same as $G$. For this case a $C_5$-colouring is given in Figure <ref>.

For the case $l_1=l_2=7$ and $l_3=l_4=9$, assuming $c'$ is the length of the common thread of the two cycles of length $9$, a similar calculation as in Case $2$ implies that $a=a'$, $b=b'$ and $c'=c+2$.
The possibilities are (i) $a=1$, $b=3$ and $c=3$, (ii) $a=1$, $b=4$ and $c=2$, (iii) $a=2$, $b=2$ and $c=3$, (iv) $a=2$, $b=3$ and $c=2$, and (v) $a=b=3$ and $c=1$. As in each case, each pair of vertices is on a common cycle of length at most $10$, and since the girth is at least $7$, $G$ must be isomorphic to $H$. Then, a mapping to $C_5$ can readily be found (see Figure <ref>). This case completes the proof as there is no counterexample to the statement of the theorem.

0.6[join=bevel,inner sep=0.6mm]

[draw,shape=circle,fill] (x) at (0,0) ;
(x) node[left=0.2cm] $0$;
[draw,shape=circle,fill] (y) at (6,0) ;
(y) node[right=0.2cm] $1$;
[draw,shape=circle,fill] (z) at (3,5.2) ;
(z) node[above=0.2cm] $1$;
[draw,shape=circle,fill] (t) at (3,1.7) ;
(t) node[above right=0.1cm] $4$;

[draw,shape=circle,fill] (a1) at (3,4) ;
(a1) node[left=0.2cm] $2$;
[draw,shape=circle,fill] (a2) at (3,2.9) ;
(a2) node[left=0.2cm] $3$;

[draw,shape=circle,fill] (b1) at (0.75,1.3) ;
(b1) node[left=0.2cm] $4$;
[draw,shape=circle,fill] (b2) at (1.5,2.6) ;
(b2) node[left=0.2cm] $3$;
[draw,shape=circle,fill] (b3) at (2.25,3.9) ;
(b3) node[left=0.2cm] $2$;

[draw,shape=circle,fill] (bp1) at (4.5,0.85) ;
(bp1) node[above=0.2cm] $0$;

[draw,shape=circle,fill] (c1) at (0.75,0.425) ;
(c1) node[above=0.2cm] $1$;
[draw,shape=circle,fill] (c2) at (1.5,0.85) ;
(c2) node[below=0.2cm] $2$;
[draw,shape=circle,fill] (c3) at (2.25,1.275) ;
(c3) node[above=0.2cm] $3$;

[draw,shape=circle,fill] (cp1) at (4.5,2.6) ;
(cp1) node[right=0.2cm] $0$;

[-,line width=0.4mm] (x)–(y)–(z)–(x)–(t)–(y)  (t)–(z);

The first graph considered in Case $3$, with $(a,b,c)=(3,4,4)$.

[$(a,b,c)=(1,3,3)$]0.6[join=bevel,inner sep=0.6mm]

[draw,shape=circle,fill] (x) at (0,0) ;
(x) node[left=0.2cm] $1$;
[draw,shape=circle,fill] (y) at (6,0) ;
(y) node[right=0.2cm] $2$;
[draw,shape=circle,fill] (z) at (3,5.2) ;
(z) node[above=0.2cm] $4$;
[draw,shape=circle,fill] (t) at (3,1.7) ;
(t) node[above right=0.1cm] $0$;

[draw,shape=circle,fill] (b1) at (1,1.7) ;
(b1) node[left=0.2cm] $2$;
[draw,shape=circle,fill] (b2) at (2,3.45) ;
(b2) node[left=0.2cm] $3$;

[draw,shape=circle,fill] (bp1) at (4,1.13) ;
(bp1) node[above=0.2cm] $4$;
[draw,shape=circle,fill] (bp2) at (5,0.57) ;
(bp2) node[above=0.2cm] $3$;

[draw,shape=circle,fill] (c1) at (1,0.57) ;
(c1) node[above=0.2cm] $0$;
[draw,shape=circle,fill] (c2) at (2,1.13) ;
(c2) node[above=0.2cm] $1$;

[draw,shape=circle,fill] (cp1) at (3.6,4.16) ;
(cp1) node[right=0.2cm] $0$;
[draw,shape=circle,fill] (cp2) at (4.2,3.12) ;
(cp2) node[right=0.2cm] $1$;
[draw,shape=circle,fill] (cp3) at (4.8,2.08) ;
(cp3) node[right=0.2cm] $0$;
[draw,shape=circle,fill] (cp4) at (5.4,1.04) ;
(cp4) node[right=0.2cm] $1$;

[-,line width=0.4mm] (x)–(y)–(z)–(x)–(t)–(y)  (t)–(z);
[$(a,b,c)=(1,4,2)$]0.6[join=bevel,inner sep=0.6mm]

[draw,shape=circle,fill] (x) at (0,0) ;
(x) node[left=0.2cm] $2$;
[draw,shape=circle,fill] (y) at (6,0) ;
(y) node[right=0.2cm] $3$;
[draw,shape=circle,fill] (z) at (3,5.2) ;
(z) node[above=0.2cm] $0$;
[draw,shape=circle,fill] (t) at (3,1.7) ;
(t) node[above right=0.1cm] $4$;

[draw,shape=circle,fill] (b1) at (0.75,1.3) ;
(b1) node[left=0.2cm] $1$;
[draw,shape=circle,fill] (b2) at (1.5,2.6) ;
(b2) node[left=0.2cm] $0$;
[draw,shape=circle,fill] (b3) at (2.25,3.9) ;
(b3) node[left=0.2cm] $1$;

[draw,shape=circle,fill] (bp1) at (3.75,1.275) ;
(bp1) node[above=0.2cm] $0$;
[draw,shape=circle,fill] (bp2) at (4.5,0.85) ;
(bp2) node[above=0.2cm] $1$;
[draw,shape=circle,fill] (bp3) at (5.25,0.425) ;
(bp3) node[above=0.2cm] $2$;

[draw,shape=circle,fill] (c1) at (1.5,0.85) ;
(c1) node[above=0.2cm] $3$;

[draw,shape=circle,fill] (cp1) at (3.75,3.9) ;
(cp1) node[right=0.2cm] $4$;
[draw,shape=circle,fill] (cp2) at (4.5,2.6) ;
(cp2) node[right=0.2cm] $0$;
[draw,shape=circle,fill] (cp3) at (5.25,1.3) ;
(cp3) node[right=0.2cm] $4$;

[-,line width=0.4mm] (x)–(y)–(z)–(x)–(t)–(y)  (t)–(z);
[$(a,b,c)=(2,2,3)$]0.6[join=bevel,inner sep=0.6mm]

[draw,shape=circle,fill] (x) at (0,0) ;
(x) node[left=0.2cm] $0$;
[draw,shape=circle,fill] (y) at (6,0) ;
(y) node[right=0.2cm] $3$;
[draw,shape=circle,fill] (z) at (3,5.2) ;
(z) node[above=0.2cm] $3$;
[draw,shape=circle,fill] (t) at (3,1.7) ;
(t) node[above right=0.1cm] $1$;

[draw,shape=circle,fill] (a1) at (3,3.4) ;
(a1) node[left=0.2cm] $2$;

[draw,shape=circle,fill] (ap1) at (3,0) ;
(ap1) node[above=0.2cm] $4$;

[draw,shape=circle,fill] (b1) at (1.5,2.6) ;
(b1) node[left=0.2cm] $4$;

[draw,shape=circle,fill] (bp1) at (4.5,0.85) ;
(bp1) node[above=0.2cm] $2$;

[draw,shape=circle,fill] (c1) at (1,0.57) ;
(c1) node[above=0.2cm] $1$;
[draw,shape=circle,fill] (c2) at (2,1.13) ;
(c2) node[above=0.2cm] $0$;

[draw,shape=circle,fill] (cp1) at (3.6,4.16) ;
(cp1) node[right=0.2cm] $4$;
[draw,shape=circle,fill] (cp2) at (4.2,3.12) ;
(cp2) node[right=0.2cm] $0$;
[draw,shape=circle,fill] (cp3) at (4.8,2.08) ;
(cp3) node[right=0.2cm] $1$;
[draw,shape=circle,fill] (cp4) at (5.4,1.04) ;
(cp4) node[right=0.2cm] $2$;

[-,line width=0.4mm] (x)–(y)–(z)–(x)–(t)–(y)  (t)–(z);
[$(a,b,c)=(2,3,2)$]0.6[join=bevel,inner sep=0.6mm]

[draw,shape=circle,fill] (x) at (0,0) ;
(x) node[left=0.2cm] $0$;
[draw,shape=circle,fill] (y) at (6,0) ;
(y) node[right=0.2cm] $2$;
[draw,shape=circle,fill] (z) at (3,5.2) ;
(z) node[above=0.2cm] $1$;
[draw,shape=circle,fill] (t) at (3,1.7) ;
(t) node[above right=0.1cm] $3$;

[draw,shape=circle,fill] (a1) at (3,3.4) ;
(a1) node[left=0.2cm] $2$;

[draw,shape=circle,fill] (ap1) at (3,0) ;
(ap1) node[above=0.2cm] $1$;

[draw,shape=circle,fill] (b1) at (1,1.7) ;
(b1) node[left=0.2cm] $1$;
[draw,shape=circle,fill] (b2) at (2,3.45) ;
(b2) node[left=0.2cm] $0$;

[draw,shape=circle,fill] (bp1) at (4,1.13) ;
(bp1) node[above=0.2cm] $4$;
[draw,shape=circle,fill] (bp2) at (5,0.57) ;
(bp2) node[above=0.2cm] $3$;

[draw,shape=circle,fill] (c1) at (1.5,0.85) ;
(c1) node[above=0.2cm] $4$;

[draw,shape=circle,fill] (cp1) at (3.75,3.9) ;
(cp1) node[right=0.2cm] $0$;
[draw,shape=circle,fill] (cp2) at (4.5,2.6) ;
(cp2) node[right=0.2cm] $4$;
[draw,shape=circle,fill] (cp3) at (5.25,1.3) ;
(cp3) node[right=0.2cm] $3$;

[-,line width=0.4mm] (x)–(y)–(z)–(x)–(t)–(y)  (t)–(z);
[$(a,b,c)=(3,3,1)$]0.6[join=bevel,inner sep=0.6mm]

[draw,shape=circle,fill] (x) at (0,0) ;
(x) node[left=0.2cm] $4$;
[draw,shape=circle,fill] (y) at (6,0) ;
(y) node[right=0.2cm] $3$;
[draw,shape=circle,fill] (z) at (3,5.2) ;
(z) node[above=0.2cm] $1$;
[draw,shape=circle,fill] (t) at (3,1.7) ;
(t) node[above right=0.1cm] $0$;

[draw,shape=circle,fill] (a1) at (3,4) ;
(a1) node[left=0.2cm] $0$;
[draw,shape=circle,fill] (a2) at (3,2.9) ;
(a2) node[left=0.2cm] $1$;

[draw,shape=circle,fill] (ap1) at (2,0) ;
(ap1) node[above=0.2cm] $0$;
[draw,shape=circle,fill] (ap2) at (4,0) ;
(ap2) node[above=0.2cm] $4$;

[draw,shape=circle,fill] (b1) at (1,1.7) ;
(b1) node[left=0.2cm] $3$;
[draw,shape=circle,fill] (b2) at (2,3.45) ;
(b2) node[left=0.2cm] $2$;

[draw,shape=circle,fill] (bp1) at (4,1.13) ;
(bp1) node[above=0.2cm] $1$;
[draw,shape=circle,fill] (bp2) at (5,0.57) ;
(bp2) node[above=0.2cm] $2$;

[draw,shape=circle,fill] (cp1) at (4,3.5) ;
(cp1) node[right=0.2cm] $0$;
[draw,shape=circle,fill] (cp2) at (5,1.75) ;
(cp2) node[right=0.2cm] $4$;

[-,line width=0.4mm] (x)–(y)–(z)–(x)–(t)–(y)  (t)–(z);

Five graphs considered in Case $3$.

We now deduce the following consequence of Theorem <ref> and Proposition <ref>, that improves the known lower bounds on $\eta(4,2)$ and $\eta(4,1)$ (noting that for larger values of $k$, the bound of Corollary <ref> is already stronger).

We have $\eta(4,1)\geq\eta(4,2)\geq 17$.

§ CONCLUDING REMARKS

In this work, we have started the study of the question of finding the smallest order of a graph of odd-girth $2k+1$ which does not map to $C_{2l+1}$. We have determined a number of previously unknown values, in particular we showed that a smallest graph of odd-girth 7 not mapping to $C_5$ is of order 15. In contrast to the result of Chvátal on the uniqueness of the smallest triangle-free 4-chromatic graph [4], we have found more than one graph of odd-girth 7 on 15 vertices which does not map to $C_5$. In fact, Gordon Royle showed computationally, that there are at least 10 such graphs.

A similar problem of interest is to ask for the order of a smallest graph of girth $g$ which does not map to $C_{2l+1}$. This question has not been studied much. In this formulation, the Grötzsch graph is the smallest graph of girth 4 which is not 3-colourable. When girth 5 is considered, then again a computational work of Gordon Royle showed that 21 vertices are needed and again the answer is not unique [18].

Our last remark is about Theorem <ref>. We think that for any given $k$, Theorem <ref> covers all values of $k$ for which $\eta(k,l)=4k$.

[1] L. Beaudou, F. Foucaud and R. Naserasr. Homomorphism bounds and edge-colourings of $K_4$-minor-free graphs. Journal of Combinatorial Theory, Series B 124:128-164, 2017.

[2] L. Beaudou, F. Foucaud, R. Naserasr and G. F. Royle. Smallest $4$-chromatic graphs of given odd-girth. Manuscript, 2016.

[3] O. V. Borodin, S. J. Kim, A. V. Kostochka and D. B. West. Homomorphisms from sparse graphs with large girth. Journal of Combinatorial Theory, Series B 90(1):147–159, 2004.

[4] V. Chvátal. The minimality of the Mycielski graph. Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), Lecture Notes in Mathematics, Vol. 406, Springer-Verlag, pp. 243–246, 1974.

[5] L. Esperet and M. Stehlík. The width of quadrangulations of the projective plane. Journal of Graph Theory 89(1):76–88, 2018.

[6] A. M. H. Gerards. Homomorphisms of graphs into odd cycles. Journal of Graph Theory 12(1):73–83, 1988.

[8] A. Gyárfás, T. Jensen and M. Stiebitz. On graphs with strongly independent colour classes. Journal of Graph Theory 46(1):1–14, 2004.

[9] F. Harary. Graph Theory. Addison-Wesley, Reading, Mass., 1969, p. 149, Exercise 12.19.

[10] P. Hell and J. Nešetřil. Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and Its Applications, Oxford University Press, 2004.

[11] T. Jiang. Small odd cycles in $4$-chromatic graphs. Journal of Graph Theory 37(2):115–117, 2001.

[13]  J. Nešetřil. In Erdős Centennial, pp. 383–407, Springer, 2013.

[14] N. V. Ngoc. On graph colorings (in Hungarian), Ph.D. Thesis, Hungarian Academy of Sciences, Budapest, 1987.

[15] N. V. Ngoc and Z. Tuza. $4$-chromatic graphs with large odd girth. Discrete Mathematics 138(1–3):387–392, 1995.

[16] A. Nilli. Short odd cycles in $4$-chromatic graphs. Journal of Graph Theory 31(2):145–147, 1999.

[17] C. Payan. On the chromatic number of cube-like graphs. Discrete Mathematics 103(3):271–277, 1992.

[18] G. F. Royle. Answer to the question “What is the smallest 4-chromatic graph of girth 5?”, http://mathoverflow.net/q/193973, 2015.

[19] M. Stiebitz. Beiträge zur Theorie der färbungskritischen Graphen (in German), Ph.D. Thesis, Technische Hochschule Ilmenau, 1985.

[20] C. Tardif. The fractional chromatic numbers of cones over graphs. Journal of Graph Theory 38(2):87–94, 2001.

[21] D. A. Youngs. $4$-chromatic projective graphs. Journal of Graph Theory 21(2):219–227, 1996.

[22] C. Q. Zhang. Circular flows of nearly eulerian graphs and vertex splitting. Journal of Graph Theory 40(3):147–161, 2002.

[23] X. Zhu. Circular chromatic number of planar graphs of large odd girth. The Electronic Journal of Combinatorics 8(1):R25, 2001.

[24] X. Zhu. Circular chromatic number, a survey. Discrete Mathematics 229(1–3):371–410, 2001.