#  $C_{2k+1}$-coloring of bounded-diameter graphs

Marta Piecyk
<EMAIL_ADDRESS>This research was funded by Polish National
Science Centre, grant no. 2022/45/N/ST6/00237. Faculty of Mathematics and
Information Science, Warsaw University of Technology

###### Abstract

For a fixed graph $H$, in the graph homomorphism problem, denoted by
$\textsc{Hom}(H)$, we are given a graph $G$ and we have to determine whether
there exists an edge-preserving mapping $\varphi:V(G)\to V(H)$. Note that
$\textsc{Hom}(C_{3})$, where $C_{3}$ is the cycle of length $3$, is equivalent
to $3$-Coloring. The question whether $3$-Coloring is polynomial-time solvable
on diameter-$2$ graphs is a well-known open problem. In this paper we study
the $\textsc{Hom}(C_{2k+1})$ problem on bounded-diameter graphs for $k\geq 2$,
so we consider all other odd cycles than $C_{3}$. We prove that for $k\geq 2$,
the $\textsc{Hom}(C_{2k+1})$ problem is polynomial-time solvable on
diameter-$(k+1)$ graphs – note that such a result for $k=1$ would be precisely
a polynomial-time algorithm for $3$-Coloring of diameter-$2$ graphs.

Furthermore, we give subexponential-time algorithms for diameter-$(k+2)$ and
-$(k+3)$ graphs.

We complement these results with a lower bound for diameter-$(2k+2)$ graphs –
in this class of graphs the $\textsc{Hom}(C_{2k+1})$ problem is NP-hard and
cannot be solved in subexponential-time, unless the ETH fails.

Finally, we consider another direction of generalizing $3$-Coloring on
diameter-$2$ graphs. We consider other target graphs $H$ than odd cycles but
we restrict ourselves to diameter $2$. We show that if $H$ is triangle-free,
then $\textsc{Hom}(H)$ is polynomial-time solvable on diameter-$2$ graphs.

##  1 Introduction

A natural approach to computationaly hard problems is to restrict the class of
input graphs, for example by bounding some parameters. One of such parameters
is the diameter, i.e., for a graph $G$, its diameter is the least integer $d$
such that for every pair of vertices $u,v$ of $G$, there is a $u$-$v$ path on
at most $d$ edges. We say that $G$ is a diameter-$d$ graph, if its diameter is
at most $d$. Recently, bounded-diameter graphs received a lot of attention
[22, 19, 24, 3, 2, 23, 9, 6]. It is known that graphs from applications often
have bounded diameter, for instance social networks tend to have bounded
diameter [28]. Furthermore, almost all graphs have diameter $2$, i.e., the
probability that a random graph on $n$ vertices has diameter $2$ tends to $1$
when $n$ tends to infinity [20]. Therefore, solving a problem on bounded-
diameter graphs captures a wide class of graphs. On the other hand, not all of
the standard approaches can be used on bounded-diameter – note that the class
of diameter-$d$ graphs is not closed under vertex deletion.

Even if we consider the class of diameter-$2$ graphs, its members can contain
any graph as an induced subgraph. Indeed, consider any graph $G$, and let
$G^{+}$ be the graph obtained from $G$ by adding a universal vertex $u$, i.e.,
we add vertex $u$ and make it adjacent to all vertices of $G$. It is
straightforward to observe that the diameter of $G^{+}$ is at most $2$. This
construction can be used for many graph problems on diameter-$2$ graphs as a
hardess reduction, which proves that they cannot be solved in subexponential
time under the ETH, for instance Max Independent Set.

The construction of $G^{+}$ also gives us a reduction from $(k-1)$-Coloring to
$k$-Coloring on diameter-$2$ graphs, and thus for any $k\geq 4$, the
$k$-Coloring problem on diameter-$2$ graphs is NP-hard and cannot be solved in
subexponential time, unless the ETH fails. Note that this argument does not
work for $k=3$ since then we reduce from $2$-Coloring, which is polynomial-
time solvable. A textbook reduction from NAE-SAT implies that for $d\geq 3$,
the $3$-Coloring problem is NP-hard and cannot be solved in subexponential-
time, unless the ETH fails [27]. Therefore, it is only interesting to study
$3$-Coloring on diameter-$2$ and -$3$ graphs. Mertzios and Spirakis proved
that $3$-Coloring is NP-hard on diameter-$3$ graphs [24]. However, the
question whether $3$-Coloring can be solved in polynomial time on diameter-$2$
graphs remains open.

For $3$-Coloring on diameter-$2$ graphs, there were given subexponential-time
algorithms, first by Mertzios and Spirakis with running time
$2^{\mathcal{O}(\sqrt{n\log{n}})}$ [24]. This was later improved by Dębski,
Piecyk, and Rzążewski, who gave an algorithm with running time
$2^{\mathcal{O}(n^{1/3}\cdot\log^{2}n)}$ [9]. They also provided a
subexponential-time algorithm for $3$-Coloring for diameter-$3$ graphs.

The $3$-Coloring problem on bounded-diameter graphs was also intensively
studied on instances with some additional restrictions, i.e., on graphs with
some forbidden induced subgraphs – and on such graph classes polynomial-time
algorithms were given [22, 19, 23].

One of the generalizations of graph coloring are homomorphisms. For a fixed
graph $H$, in the graph homomorphism problem, denoted by $\textsc{Hom}(H)$, we
are given a graph $G$, and we have to determine whether there exists an edge-
preserving mapping $\varphi:V(G)\to V(H)$, i.e., for every $uv\in E(G)$, it
holds that $\varphi(u)\varphi(v)\in E(H)$. Observe that for $K_{k}$ being a
complete graph on $k$ vertices, the $\textsc{Hom}(K_{k})$ problem is
equivalent to $k$-Coloring. Observe that the problem is trivial when $H$
contains a vertex $x$ with a loop since we can map all vertices of $G$ to $x$.
In case when $H$ is bipartite, in fact we have to verify whether $G$ is
bipartite and this can be done in polynomial time. Hell and Nešetřil proved
that for all other graphs $H$, i.e., loopless and non-bipartite, the
$\textsc{Hom}(H)$ problem is NP-hard [18]. Such a complete dichotomy was
provided by Feder, Hell, and Huang also for the list version of the problem
[13]. The graph homomorphism problem and its variants in various graph classes
and under various parametrizations received recently a lot of attention [25,
15, 14, 4, 5, 7, 8, 14, 26, 17]. We also point out that among all target
graphs $H$, a lot of attention received odd cycles [16, 1, 10, 29, 21]. Note
that the cycle on $5$ vertices is the smallest graph $H$ such that the
$\textsc{Hom}(H)$ problem is not equivalent to graph coloring.

Our contribution. In this paper we consider the $\textsc{Hom}(C_{2k+1})$
problem on bounded-diameter graphs, where $C_{2k+1}$ denotes the cycle on
$2k+1$ vertices. Note that for $k=1$, we have $C_{3}$, so this problem is
equivalent to $3$-Coloring. In this work we consider all other values of $k$.
Our first result is a polynomial-time algorithm for $\textsc{Hom}(C_{2k+1})$
on diameter-$(k+1)$ graphs.

######  Theorem 1.

Let $k\geq 2$. Then $\textsc{Hom}(C_{2k+1})$ can be solved in polynomial time
on diameter-$(k+1)$ graphs.

Note that such a result for $k=1$ would yield a polynomial-time algorithm for
$3$-Coloring on diameter-$2$ graphs. Let us discuss the crucial points where
this algorithm cannot be applied directly for $k=1$. The first property, which
holds for every cycle except $C_{3}$ and $C_{6}$, is that if for some set $S$
of vertices, any two of them have a common neighbor, then there is a vertex
that is a common neighbor of all vertices of $S$. Furthermore, for every cycle
of length at least $5$ except $C_{6}$, for a set $S$ of $3$ vertices, every
vertex of $S$ has a private neighbor with respect to $S$, i.e., a neighbor
that is non-adjacent to any other vertex of $S$.

We first show that for an instance of $\textsc{Hom}(C_{2k+1})$, for each
vertex $v$ we can deduce the set of vertices it can be mapped to and define a
list of $v$ – all lists are of size at most $3$. The properties discussed
above allow us to encode coloring of a vertex with list of size $3$ using its
neighbors with lists of size two, and such a reduced instance of a slightly
more general problem (we have more constraints than just the edges, but all of
them are binary) can be solved in polynomial time by reduction to $2$-SAT,
similar to the one of Edwards [11].

Furthermore, we give subexponential-time algorithms.

######  Theorem 2.

Let $k\geq 2$. Then $\textsc{Hom}(C_{2k+1})$ can be solved in time:

  1. (1.)

$2^{\mathcal{O}((n\log{n})^{\frac{k+1}{k+2}})}$ on diameter-$(k+2)$ $n$-vertex
graphs,

  2. (2.)

$2^{\mathcal{O}((n\log{n})^{\frac{k+2}{k+3}})}$ on diameter-$(k+3)$ $n$-vertex
graphs.

Here the branching part of the algorithm is rather standard. The more involved
part is to show that after applying braching and reduction rules we are left
with an instance that can be solved in polynomial time. Similar to Theorem 1,
we first analyze the lists of all vertices, and then reduce to an instance of
more general problem where every vertex has list of size at most $2$.

We complement Theorem 1 and Theorem 2 with the following lower bound.

######  Theorem 3.

Let $k\geq 2$. Then $\textsc{Hom}(C_{2k+1})$ is NP-hard on diameter-$(2k+2)$
graphs (of radius $k+1$) and cannot be solved in subexponential time, unless
the ETH fails.

We summarize the current state of knowledge about the complexity of
$\textsc{Hom}(C_{2k+1})$ in Table 1.

$k$ / $\operatorname{diam}$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | $\geq 10$
---|---|---|---|---|---|---|---|---|---|---
1 | P | S | S, NP-h | NS | NS | NS | NS | NS | NS | NS
2 | P | P | P | S | S | NS | NS | NS | NS | NS
3 | P | P | P | P | S | S | ? | ? | NS | NS
4 | P | P | P | P | P | S | S | ? | ? | NS
$\geq 5$ | P | P | P | P | P | P | S | S | ? | ?
Table 1: Complexity of $\textsc{Hom}(C_{2k+1})$ on bounded-diameter graphs.
The symbol in the cell $(k,d)$ denotes that $\textsc{Hom}(C_{2k+1})$ on
diameter-$d$, respectively, P – is polynomial-time solvable, NP-h – is NP-
hard, S – can be solved in subexponential time, and NS – cannot be solved in
subxponential time assuming the ETH. The rows for $k\geq 2$ are filled due to
Theorem 1, Theorem 2, and Theorem 3. The first row is based on [24, 9].

The next direction we study in the paper is the following. Instead of
considering larger odd cycles and apropriate diameter, we focus on
diameter-$2$ input graphs, but we change the target graph to some arbitrary
$H$. Note that it only makes sense to consider graphs $H$ of diameter-$2$,
since the homomorphic image of a diameter-$2$ graph has to induce a
diameter-$2$ subgraph. We provide a polynomial-time algorithm for triangle-
free target graphs. We point out that the class of triangle-free diameter-$2$
graphs is still very rich, for instance, contains all Mycielski graphs.

######  Theorem 4.

Let $H$ be a triangle-free graph. Then the $\textsc{Hom}(H)$ problem can be
solved in polynomial time on diameter-$2$ graphs.

Finally, let us point out that we actually prove stronger statements of
Theorem 1, Theorem 2, Theorem 4 as we consider more general list version of
the problem.

##  2 Preliminaries

For a vertex $v$, by $N_{G}(v)$ we denote the neighborhood of $v$ in $G$. By
$\operatorname{dist}_{G}(u,v)$ we denote the length (number of edges) of a
shortest $u$-$v$ path in $G$. For a positive integer $d$, by $N^{\leq
d}_{G}(v)$ we denote the set of all vertices $u\in V(G)$ such that
$\operatorname{dist}_{G}(u,v)\leq d$. If $G$ is clear from the contex, we omit
the subscript $G$ and simply write $N(v)$, $N^{\leq d}(v)$, and
$\operatorname{dist}(u,v)$. A _diameter_ of $G$, denoted by
$\operatorname{diam}(G)$, is the maximum $\operatorname{dist}(u,v)$ over all
pairs of vertices $u,v\in V(G)$. We say that $G$ is _diameter- $d$_ graph if
$\operatorname{diam}(G)\leq d$. A _radius_ of $G$ is the minimum integer $r$
such that there is a vertex $z\in V(G)$ such that for every $v\in V(G)$, it
holds that $\operatorname{dist}(v,z)\leq r$. By $[n]$ we denote the set
$\\{1,2,\ldots,n\\}$ and by $[n]_{0}$ we denote $\\{0,1,\ldots,n\\}$.
Throughout this paper all graphs we consider are simple, i.e., no loops, no
multiple edges.

Homomorphisms. For graphs $G,H$, a homomorphism from $G$ to $H$ is an edge-
preserving mapping $\varphi:V(G)\to V(H)$, i.e., for every $uv\in E(G)$, it
holds $\varphi(u)\varphi(v)\in E(H)$. For fixed $H$, called _target_ , in the
homomorphism problem, denoted by $\textsc{Hom}(H)$, we are given a graph $G$,
and we have to determine whether there exists a homomorphism from $G$ to $H$.
In the list homomorphism problem, denoted by $\textsc{LHom}(H)$, $G$ is given
along with lists $L:V(G)\to 2^{V(H)}$, and we have to determine if there is a
homomorphism $\varphi$ from $G$ to $H$ which additionally respects lists,
i.e., for every $v\in V(G)$ it holds $\varphi(v)\in L(v)$. We will write
$\varphi:G\to H$ (resp. $\varphi:(G,L)\to H$) if $\varphi$ is a (list)
homomorphism from $G$ to $H$, and $G\to H$ (resp. $(G,L)\to H$) to indicate
that such a (list) homomorphism exists. Since graph homomorphism generalize
graph colorings we will often refer to homomorphism as coloring and to
vertices of $H$ as colors.

Cycles. Whenever $C_{2k+1}$ is the target graph, we will denote its vertex set
by $[2k]_{0}$, unless stated explicitly otherwise. Moreover, whenever we refer
to the vertices of the $(2k+1)$-cycle, i.e., cycle on $2k+1$ vertices, by $+$
and $-$ we denote respectively the addition and the subtraction modulo $2k+1$.

Lists. For an instance $(G,L)$ of $\textsc{LHom}(C_{2k+1})$, by $V_{i}$ we
denote the set of vertices $v$ of $G$ such that $|L(v)|=i$. Sometimes we will
refer to vertices of $V_{1}$ as _precolored vertices_. We also define $V_{\geq
i}=\bigcup_{j\geq i}V_{j}$. We say that a list $L(v)$ is _of type
$(\ell_{1},\ldots,\ell_{r})$_ if $|L(v)|=r+1$ and its vertices can be ordered
$c_{0},\ldots,c_{r}$ so that for every $i\in[r-1]_{0}$, we have that
$c_{i+1}=c_{i}+\ell_{i}$. For example, for $k\geq 4$, one of the types of the
list $\\{1,4,6,7\\}$ is $(3,2,1)$.

Binary CSP and $2$-SAT. For a given set (domain) $D$, in the Binary Constraint
Satisfaction problem (BCSP) we are given a set $V$ of variables, list function
$L:V\to 2^{D}$, and constraint function $C:V\times V\to 2^{D\times D}$. The
task is to determine whether there exists an assignment $f:V\to D$ such that
for every $v\in V$, we have $f(v)\in L(v)$ and for every pair $(u,v)\in
V\times V$, we have $(f(u),f(v))\in C(u,v)$. Clearly, any instance of
$\textsc{LHom}(H)$ can be seen as an instance of BCSP, where the domain $D$ is
$V(H)$, list function remains the same, and for every edge $uv\in E(G)$ we set
$C(u,v)=\\{(x,y)\ |\ xy\in E(H)\\}$ and for every $uv\notin E(G)$ we set
$C(u,v)=V(H)\times V(H)$. We will denote by $\operatorname{BCSP}(H,G,L)$ the
instance of BCSP corresponding to the instance $(G,L)$ of $\textsc{LHom}(H)$.
Standard approach of Edwards [11] with a reduction to 2-SAT implies that in
polynomial time we can solve an instance of BCSP with all list of size at most
two.

######  Theorem 5 (Edwards[11]).

Let $(V,L,C)$ be an instance of BCSP over the domain $D$. Assume that for
every $v\in V$ it holds $|L(v)|\leq 2$. Then we can solve the instance
$(V,L,C)$ in polynomial time.

##  3 Reduction rules and basic observations

In this section we define reduction rules and show some basic observations.

Reduction rules. Let $H$ be a graph and let $(G,L)$ be an instance of
$\textsc{LHom}(H)$. We define the following reduction rules.

  1. (R1)

If $H=C_{2k+1}$ and $G$ contains an odd cycle of length at most $2k-1$, then
return NO.

  2. (R2)

If $H=C_{2k+1}$ and in $G$ there are two $(2k+1)$-cycles with consecutive
vertices respectively $c_{0},\ldots,c_{2k}$ and
$c^{\prime}_{0},\ldots,c^{\prime}_{2k}$ and such that $c_{0}=c_{0}^{\prime}$
and $c_{i}=c_{j}^{\prime}$ for some $i,j\neq 0$, then a) if $i=j$, then
contract $c_{\ell}$ with $c^{\prime}_{\ell}$ for every $\ell\in[2k]$, b) if
$i=-j$, then contract $c_{\ell}$ with $c^{\prime}_{(-\ell)}$ for every
$\ell\in[2k]$, c) otherwise return NO.

  3. (R3)

For every edge $uv$, if there is $x\in L(u)$ such that $N_{H}(x)\cap
L(v)=\emptyset$, then remove $x$ from $L(u)$.

  4. (R4)

If there is $v\in V(G)$ such that $L(v)=\emptyset$, then return NO.

  5. (R5)

For every $v\in V(G)$, if there are $x,y\in L(v)$ such that for every $u\in
N_{G}(v)$, we have $N_{H}(x)\cap L(u)\subseteq N_{H}(y)\cap L(u)$, then remove
$x$ from $L(v)$.

  6. (R6)

For a vertex $x\in V(H)$, and vertices $u,v\in V(G)$ such that
$L(u)=L(v)=\\{x\\}$, if $uv\in E(G)$, then return NO, otherwise contract $u$
with $v$.

Clearly, each of the above reduction rules can be applied in polynomial time.
Let us verify that the reduction rules are safe.

######  Lemma 1.

After applying each reduction rule to an instance $(G,L)$ of
$\textsc{LHom}(H)$, we obtain an equivalent instance.

###### Proof.

First, any odd cycle cannot be mapped to a larger odd cycle, so the reduction
rule (R1) is safe. Furthermore, for any $(2k+1)$-cycle, in any list
homomorphism to $C_{2k+1}$, its consecutive vertices have to be mapped to
consecutive vertices of $C_{2k+1}$. Let $c_{0},\ldots,c_{2k}$ and
$c^{\prime}_{0},\ldots,c^{\prime}_{2k}$ be the vertices of two $(2k+1)$-cycles
such that $c_{0}=c_{0}^{\prime}$ and $c_{i}=c_{j}^{\prime}$ for some $i,j\neq
0$. Suppose we are dealing with a yes-instance and let $\varphi:(G,L)\to
C_{2k+1}$. Without loss of generality assume that
$\varphi(c_{0})=\varphi(c_{0}^{\prime})=0$ and
$\varphi(c_{i})=\varphi(c_{j}^{\prime})=i$. Then $\varphi(c_{s})=s$ for every
$s\in[2k]_{0}$. Moreover, either $j=i$ or $j=-i$, and
$\varphi(c_{s}^{\prime})=s$ for every $s\in[2k]_{0}$ in the first case, or
$\varphi(c_{s}^{\prime})=-s$ for every $s\in[2k]_{0}$ in the second case.
Therefore, the reduction rule (R2) is safe.

Let $uv\in E(G)$ be such that there is $x\in L(u)$ such that $N(x)\cap
L(v)=\emptyset$. Suppose that there is a list homomorphism $\varphi:(G,L)\to
C_{2k+1}$ such that $\varphi(u)=x$. Then $v$ must be mapped to a vertex from
$N(x)\cap L(v)=\emptyset$, a contradiction. Thus we can safely remove $x$ from
$L(u)$, and (R3) is safe. Clearly, if any list of a vertex is an empty set,
then we are dealing with a no-instance and thus (R4) is safe. Finally, assume
there is $v\in V(G)$ and $x,y\in L(v)$ such that for every $u\in N_{G}(v)$, it
holds $N_{H}(x)\cap L(u)\subseteq N_{H}(y)\cap L(u)$, and suppose there is a
list homomorphism $\varphi:(G,L)\to H$ such that $\varphi(v)=x$. Then
$\varphi^{\prime}$ defined so that $\varphi^{\prime}(v)=y$ and
$\varphi^{\prime}(w)=\varphi(w)$ for $w\in V(G)\setminus\\{v\\}$ is also a
list homomorphism $(G,L)\to H$. Therefore, (R5) is safe. If two vertices have
the same one-element list, then they must be mapped to the same vertex. Since
we only consider loopless graphs $H$, adjacent vertices of $G$ cannot be
mapped to the same vertex. Therefore, if two vertices $u,v$ of $G$ have lists
$L(v)=L(u)=\\{x\\}$ for some $x\in V(H)$, then if $uv\in E(G)$ we are dealing
with a no-instance. Otherwise, we can contract $u$ and $v$ and thus (R6) is
safe. ∎

In the following observation we describe the lists of vertices that are at
some small distance of a precolored vertex.

######  Observation 1.

Let $k\geq 2$ and let $(G,L)$ be an instance of $\textsc{LHom}(C_{2k+1})$. Let
$u\in V(G)$ be such that $L(u)=\\{i\\}$ and let $v\in V(G)$ be such that
$\operatorname{dist}(u,v)=d$. If none of the reduction rules can be applied,
then

  1. a)

$L(v)\subseteq\\{i-d,i-d+2,\ldots,i-2,i,i+2,\ldots,i+d-2,i+d\\}$ if $d$ is
even,

  2. b)

$L(v)\subseteq\\{i-d,i-d+2,\ldots,i-1,i+1,\ldots,i+d-2,i+d\\}$ if $d$ is odd.

###### Proof.

Let $P$ be a shortest $u$-$v$ path such that the consecutive vertices of $P$
are $u=p_{0},p_{2},\ldots,p_{d}=v$. We have $L(p_{0})=\\{i\\}$. Since the
reduction rule (R3) cannot be applied for $p_{0}p_{1}$, we must have
$L(p_{1})\subseteq\\{i-1,i+1\\}$. Applying this reasoning to consecutive
vertices of the path, for $j\in[d]$, we must have

$L(v)\subseteq\\{i-j,i-j+2,\ldots,i-2,i,i+2,\ldots,i+j-2,i+j\\},$

if $j$ is even,

$L(v)\subseteq\\{i-j,i-j+2,\ldots,i-1,i+1,\ldots,i+j-2,i+j\\},$

if $j$ is odd, which completes the proof. ∎

The next observation immediately follows from 1.

######  Observation 2.

Let $k\geq 2$ and let $(G,L)$ be an instance of $\textsc{LHom}(C_{2k+1})$. Let
$u,w\in V(G)$ be such that $L(u)=\\{i\\}$ and $L(w)=\\{i+1\\}$. Let $v\in
V(G)$ be such that $\operatorname{dist}(u,v)=\operatorname{dist}(w,v)=k+\ell$.
If none of the reduction rules can be applied, then
$L(v)\subseteq\\{i+k-\ell+1,i+k-\ell+2,\ldots,i+k+\ell+1\\}$.

In the following observation we show that for a partial mapping $\varphi:G\to
C_{2k+1}$ for $k\geq 2$, for some vertex $v\in V(G)$, if every pair $(a,b)$ of
its neighbors is precolored so that $\varphi(a)$ and $\varphi(b)$ have a
common neighbor in $L(v)$, then $\varphi$ can be extended to $v$ so that it
preserves the edges containing $v$.

######  Observation 3.

Let $k\geq 2$, let $(G,L)$ be an instance of $\textsc{LHom}(C_{2k+1})$ and let
$v\in V(G)$. Let $\varphi:N(v)\to[2k]_{0}$ be a mapping such that for every
$a,b\in N(v)$, we have that $N_{C_{2k+1}}(\varphi(a))\cap
N_{C_{2k+1}}(\varphi(b))\cap L(v)\neq\emptyset$. Then $\bigcap_{u\in
N(v)}N_{C_{2k+1}}(\varphi(u))\cap L(v)\neq\emptyset$.

###### Proof.

Define $A=\\{\varphi(u)\ |\ u\in N(v)\\}$. If $|A|\leq 2$, then the statement
clearly follows. We will show that this is the only case. So suppose that
$|A|\geq 3$. If two distinct vertices of $C_{2k+1}$ for $k\geq 2$ have a
common neighbor, then they must be at distance exactly two. Without loss of
generality, let $0,2\in A$ and $1\in L(v)$. Moreover, let $i\in
A\setminus\\{0,2\\}$. By assumption $N_{C_{2k+1}}(i)\cap
N_{C_{2k+1}}(0)\neq\emptyset$, so $i=2k-1$. On the other hand,
$N_{C_{2k+1}}(i)\cap N_{C_{2k+1}}(2)\neq\emptyset$, so $i=4$. Thus $2k-1=4$, a
contradiction. ∎

In the next observation we show that for an odd cycle $C$ and a vertex $v$
there is at least one pair of consecutive vertices of $C$ with equal distances
to $v$.

######  Observation 4.

Let $G$ be a connected graph, let $C$ be a cycle in $G$ with consecutive
vertices $c_{0},\ldots,c_{2k}$, and let $v\in V(G)\setminus V(C)$. Then there
is $i\in[2k]_{0}$ such that
$\operatorname{dist}(v,c_{i})=\operatorname{dist}(v,c_{i+1})$.

###### Proof.

First observe, that for all $i$, we have
$|\operatorname{dist}(v,c_{i})-\operatorname{dist}(v,c_{i+1})|\leq 1$ since
$c_{i}c_{i+1}\in E(G)$. Therefore, going around the cycle the distance from
$v$ to $c_{i}$ can increase by 1, decrease by 1, or remain the same. Since we
have to end up with the same value at the end and the length of the cycle is
odd, there is at least one pair of consecutive vertices $c_{i},c_{i+1}$ such
that $\operatorname{dist}(v,c_{i})=\operatorname{dist}(v,c_{i+1})$. ∎

##  4 Polynomial-time algorithms

In this section we prove Theorem 1. In fact we prove a stronger statement for
the list version of the problem.

######  Theorem 6.

Let $k\geq 2$. Then $\textsc{LHom}(C_{2k+1})$ can be solved in polynomial time
on diameter-$(k+1)$ graphs.

###### Proof.

Let $(G,L)$ be an instance of $\textsc{LHom}(C_{2k+1})$ such that $G$ has
diameter at most $k+1$. First for every $i\in[2k]_{0}$ we check whether there
is a list homomorphism $\varphi:(G,L)\to C_{2k+1}$ such that no vertex is
mapped to $i$, so we look for a list homomorphism to a path which can be done
in polynomial time by [12].

If there is no such a homomorphism, then we know that all colors have to be
used and thus we guess $2k+1$ vertices that will be mapped to distinct
vertices of $C_{2k+1}$. Let $c_{0},\ldots,c_{2k}$ be the vertices such that
$c_{i}$ is precolored with $i$. We check whether such a partial assignment
satisfies the edges with both endpoints precolored. Moreover, for $u,v$ that
are mapped to $i,i+1$, respectively, if $uv$ are non-adjacent, we add the edge
$uv$ – this operation is safe as $uv$ are precolored with consecutive vertices
of $C_{2k+1}$ and adding an edge does not increase the diameter. Finally, we
exhaustively apply the reduction rules.

Observe that the vertices $c_{0},\ldots,c_{2k}$ induce a $(2k+1)$-cycle $C$.
Suppose there is a vertex $v$ that after the above procedure is not on $C$. By
4, there is $i\in[2k]_{0}$ such that
$\operatorname{dist}(v,c_{i})=\operatorname{dist}(v,c_{i+1})=:\ell$.

First we show that we cannot have $\ell\leq k$. Suppose otherwise. Let
$P_{1},P_{2}$ be shortest $v$-$c_{i}$-, and $v$-$c_{i+1}$-paths, respectively.
Let $u$ be the their last common vertex (it cannot be $c_{i}$ or $c_{i+1}$ as
the distances are the same and $c_{i},c_{i+1}$ are adjacent). Note that since
$P_{1}$, $P_{2}$ are shortest, the $u$-$c_{i}$-path $P_{1}^{\prime}$ obtained
from $P_{1}$ and the $u$-$c_{i+1}$-path $P_{2}^{\prime}$ obtained from $P_{2}$
have the same length. Therefore we can construct a cycle by taking
$P_{1}^{\prime},P_{2}^{\prime}$ and the edge $c_{i}c_{i+1}$. The length of the
cycle is odd, and it is at most $2k+1$. This cycle contains at least two
vertices from $C$, so either it should be contracted by (R2) or (R1) would
return NO. Therefore we cannot have $\ell\leq k$, and thus, since
$\operatorname{diam}(G)\leq k+1$, we have $\ell=k+1$.

By 2, we have that $L(v)\subseteq\\{i+k,i+k+1,i+k+2\\}$. Furthermore, if
$|L(v)|=3$ and (R3) cannot be applied, the possible lists of the neighbors of
$v$ are $\\{i+k,i+k+1\\}$, $\\{i+k+1,i+k+2\\}$, $\\{i+k-1,i+k,i+k+1\\}$,
$\\{i+k,i+k+1,i+k+2\\}$, and $\\{i+k+1,i+k+2,i+k+3\\}$.

Therefore, all lists of our instance have size at most 3. By the above
considerations, each vertex of $V_{3}$ has list of type $(1,2)$. Moreover, for
a vertex with list $\\{j,j+1,j+2\\}$, the possible lists of its neighbors in
$G[V_{3}]$ are then $\\{j-1,j,j+1\\}$, $\\{j,j+1,j+2\\}$, and
$\\{j+1,j+2,j+3\\}$. For a list $L=\\{i,j,r\\}$ of type $(1,2)$, where $i$ is
the vertex such that $i=j+1$ and $i=r-1$, we will call $i$ the _middle vertex_
of $L$.

Now consider a connected component $S$ of $G[V_{3}]$. Note that coloring one
vertex $v$ almost fixes the coloring of the whole component, i.e., if $v$ is
colored with the middle vertex from its list, then all its neighbors with
different lists have to be colored with their middle vertices from their
lists. Moreover, for the vertices with the same list as $v$, we know whether
they are colored with the middle vertex or not. Therefore, we can check two
posibilites of coloring one vertex, and then solve the subinstance, where each
vertex has list of size at most two, so it can be done in polynomial time by
Theorem 5. If for some component in both cases we obtain NO, then we return
NO.

Creating a BCSP instance. Let
$(V(G),L,C)=\operatorname{BCSP}(C_{2k+1},G[V_{1}\cup V_{2}],L)$. We will
modify now the instance $(V(G),L,C)$ so it is equivalent to the instance
$(G,L)$. For every $v\in V_{3}$ and for every pair of $a,b\in N(v)\cap V_{2}$,
we leave in $C(a,b)$ only these pairs of vertices that have a common neighbor
in $L(v)$ – recall that by 3 this ensures us that there will be color left for
$v$. Finally, for every connected component $C$ of $G[V_{3}]$, we add
constraints according to which of the two possibilities $C$ can be properly
colored, i.e., for $v$ with list $\\{i,i+1,i+2\\}$, its neighors in $V_{2}$
have lists $\\{i,i+1\\}$ and $\\{i+1,i+2\\}$, and if $C$ cannot be properly
colored so that $v$ is colored with $i+1$, we remove $i$ and $i+2$ from the
list of neigbors of $v$, and if $C$ cannot be properly colored so that $v$ is
colored with one of $i,i+2$, we remove $i+1$ from the list of neigbors of $v$.
This completes the construction of BCSP instance $(V(G),L,C)$. By Theorem 5 we
solve $(V(G),L,C)$ in polynomial time.

Correctness. It remains to show that $(V(G),L,C)$ is equivalent to $(G,L)$.
First suppose that there is a list homomorphism $\varphi:(G,L)\to C_{2k+1}$.
Let us define $f=\varphi|_{V_{1}\cup V_{2}}$. Clearly $f$ respects the lists
and the constraints coming from $\operatorname{BCSP}(C_{2k+1},G,L)$.
Furthermore, since $\varphi$ is a homomorphism, for every $v\in V_{3}$ and
every pair $u,w\in V_{2}$ of neighbors of $v$, it holds that $f(u)$ and $f(w)$
have a common neighbor in $L(v)$. Finally, let $S$ be a connected component of
$G[V_{3}]$, let $v\in V(S)$ with $L(v)=\\{i,i+1,i+2\\}$, and let $u,w$ be
neighbors of $v$ with lists, respectively $\\{i,i+1\\}$ and $\\{i+1,i+2\\}$.
Suppose that $(f(u),f(w))\notin C(u,w)$ because of the last step in the
construction of $(V(G),L,C)$. Then either $f(u)=i$ and $f(w)=i+2$ or
$f(u)=f(w)=i$. In the first case $\varphi(v)=i+1$, which contradicts the fact
that $S$ cannot be colored so that $v$ is mapped to $i+1$ and in the second
case $\varphi(v)\in\\{i,i+2\\}$, which is also a contradiction.

So now suppose that there is $f:V(G)\to[2k]_{0}$ that satisfies all
constraints of $(V(G),L,C)$. Define $\varphi(v)=f(v)$ for $v\in V_{1}\cup
V_{2}$. Note that since $f$ satisfies all constraints, $\varphi$ is a list
homomorphism on $G[V_{1}\cup V_{2}]$. We have to show that $\varphi$ can be
extended to vertices of $V_{3}$. Consider a connected component $S$ of
$G[V_{3}]$. Since the algorithm did not return NO, there is a list
homomorphism from $(S,L)$ to $C_{2k+1}$. First note that for any $v\in V_{3}$
its neighbors from $V_{2}$ are colored so that there is a color left on $L(v)$
for $v$. Moreover, if $L(v)=\\{i,i+1,i+2\\}$, then either all neigbors of $v$
in $V_{2}$ are colored with $i+1$ or with $i$ and $i+2$. In both cases, since
the neighbors of $v$ in $V_{2}$ satisfy the constraints introduced in the last
step, this means that $S$ can be properly colored so that the edges between
$V_{2}$ and $V_{3}$ are properly colored. This completes the proof. ∎

##  5 Subexponential-time algorithms

In this section we prove the following stronger version of Theorem 2

######  Theorem 7.

Let $k\geq 3$. Then $\textsc{LHom}(C_{2k+1})$ can be solved in time:

  1. (1.)

$2^{\mathcal{O}((n\log{n})^{\frac{k+1}{k+2}})}$ on $n$-vertex diameter-$(k+2)$
graphs,

  2. (2.)

$2^{\mathcal{O}((n\log{n})^{\frac{k+2}{k+3}})}$ on $n$-vertex diameter-$(k+3)$
graphs.

We start with defining branching rules crucial for our algorithm.

Branching rules. Let $k\geq 2$, let $(G,L)$ be an instance of
$\textsc{LHom}(C_{2k+1})$ and let $d\geq\operatorname{diam}(G)$. Let
$\mu=\sum_{\ell=2}^{2k+1}|V_{\ell}|$. We define the following branching rules.

  1. (B1)

If there is a vertex $v\in V_{\geq 2}$ with at least $(\mu\log\mu)^{1/d}$
neighbors in $V_{\geq 2}$ and for $a\in L(v)$, we branch on coloring $v$ with
$a$ or not, i.e., we create two instances $I_{a}=(G,L_{a})$,
$I_{a}^{\prime}=(G,L^{\prime}_{a})$ such that
$L_{a}(u)=L_{a}^{\prime}(u)=L(u)$ for every $u\in V(G)\setminus\\{v\\}$, and
$L_{a}(v)=\\{a\\}$ and $L_{a}^{\prime}(v)=L(v)\setminus\\{a\\}$.

  2. (B2)

We pick a vertex $v$ and branch on the coloring of $N^{\leq d-1}[v]\cap
V_{\geq 2}$, i.e., for every mapping $f$ of $N^{\leq d-1}[v]\cap V_{\geq 2}$
that respects the lists, we create a new instance $I_{f}=(G,L_{f})$ such that
$L_{f}(u)=L(u)$ for $u\notin N^{\leq d-1}[v]\cap V_{\geq 2}$ and
$L_{f}(w)=\\{f(w)\\}$ for $w\in N^{\leq d-1}[v]\cap V_{\geq 2}$.

Algorithm Recursion Tree. Let us describe an algorithm that for fixed $d$
takes an instance $(G,L)$ of $\textsc{LHom}(C_{2k+1})$ with a fixed precolored
$(2k+1)$-cycle $C$ and such that $\operatorname{diam}(G)\leq d$, and returns a
rooted tree $\mathcal{R}$ labelled with instances of
$\textsc{LHom}(C_{2k+1})$. We first introduce the root $r$ of $\mathcal{R}$
and we label it with $(G,L)$. Then for every node we proceed recursively as
follows. Let $s$ be a node labelled with an instance $(G^{\prime},L^{\prime})$
of $\textsc{LHom}(C_{2k+1})$. We first exhaustively apply to
$(G^{\prime},L^{\prime})$ reduction rules and if some of the reduction rules
returns NO, then $s$ does not have any children. Otherwise, if possible, we
apply branching rule (B1). We choose $a\in L(v)$ for (B1) as follows. If on
$N_{G^{\prime}[V_{\geq 2}]}(v)$ there are no lists of type $(2)$, then we take
any $a\in L(v)$. Otherwise, let $S$ be the most frequent list of type $(2)$ on
$N_{G^{\prime}[V_{\geq 2}]}(v)$, and let $S=\\{j-1,j+1\\}$ for some
$j\in[2k]_{0}$. Then we take any $a\in L(v)\setminus\\{j\\}$. After
application of (B1), we exhausively apply reduction rules (R3)–(R6) to each
instance. Furthermore, for each instance created by (B1), we create a child
node of $s$ and we label it with that instance. If (B1) cannot be applied and
if $d=k+2$, then we apply the reduction rule (B2) once, we exhausively apply
reduction rules (R3)–(R6), and again for each instance created by (B2), we
introduce a child node of $s$. The choice of $v$ is not completely arbitrary.
If possible, we choose $v$ so that
$\operatorname{dist}(v,C)\geq\lceil\frac{d}{2}\rceil$ – note that the cycle
$C$ is present in all instances of $\mathcal{R}$. In case of $d=k+3$, we
choose a vertex $v$ for every $i\in[2k]_{0}$ such that
$\operatorname{dist}(v,c_{i})=\operatorname{dist}(v,c_{i+1})=d$, and for each
such $v$, we apply the branching rule (B2) and exhausively reduction rules
(R3)–(R6), and the children of $s$ are those introduced for all instances
created in all applications of (B2). In both cases, we do not recurse on the
children of $s$ for which we applied (B2).

Let us analyze the running time of the algorithm Recursion Tree and properties
of the constructed tree $\mathcal{R}$.

######  Lemma 2.

Given an instance $(G,L)$ of $\textsc{LHom}(C_{2k+1})$ with a fixed precolored
$(2k+1)$-cycle $C$ and such that $n=|V(G)|$, $\operatorname{diam}(G)\leq d$,
the algorithm Recursion Tree in time $2^{\mathcal{O}(n^{\frac{d-1}{d}})}$
returns a tree $\mathcal{R}$ whose nodes are labelled with instances of
$\textsc{LHom}(C_{2k+1})$ and $(G,L)$ is a yes-instance if and only if at
least one instance corresponding to a leaf of $\mathcal{R}$ is a yes-instance.

###### Proof.

First we show that for every node $s$ of $\mathcal{R}$ the corresponding
instance is a yes-instance if and only if at least one instance corresponding
to a child of $s$ is a yes-instance. Let $s$ be a node of $\mathcal{R}$ and
let $(G^{\prime},L^{\prime})$ be the corresponding instance. The algorithm
Recursion Tree applies first reduction rules to $(G^{\prime},L^{\prime})$ and
by Lemma 1, we obtain equivalent instance. Furthermore, we applied to
$(G^{\prime},L^{\prime})$ either (B1) or (B2) where the branches correspond to
all possible colorings of some set of vertices so indeed
$(G^{\prime},L^{\prime})$ is a yes-instance if and only if at least one
instance corresponding to a child of $s$ is a yes-instance. Since the root of
$\mathcal{R}$ is labelled with $(G,L)$, we conclude that $(G,L)$ is a yes-
instance if and only if at least one instance corresponding to a leaf of
$\mathcal{R}$ is a yes-instance.

It remains to analyze the running time. Let $F(\mu)$ be the upper bound on the
running time of Recursion Tree applied to an instance
$(G^{\prime},L^{\prime})$ with $\mu=\sum_{\ell=2}^{2k+1}|V_{\ell}|$. Let
$p(n)$ be a polynomial such that the reduction rules can be exhaustively
applied to an instance on $n$ vertices in time $p(n)$ – note that each
reduction rule either decreases the number of vertices/sizes of lists or
returns NO, so indeed exhaustive application of reduction rules can be
performed in polynomial time. Observe that if we apply (B1) to
$(G^{\prime},L^{\prime})$, then

$F(\mu)\leq F\left(\mu-\frac{(\mu\log\mu)^{1/d}}{2k+1}\right)+F(\mu-1)+2\cdot
p(n).$

Indeed, let $v$ be the vertex to which we apply (B1). If there are no lists of
type $(2)$ on $N_{G^{\prime}[V_{\geq 2}]}(v)$, then in the branch where we set
$L(v)=\\{a\\}$ we decrease sizes of all lists on $N_{G^{\prime}[V_{\geq
2}]}(v)$. Otherwise, we chose $a\in L(v)\setminus\\{j\\}$, where
$\\{j-1,j+1\\}$ is the most frequent list of type $(2)$ on
$N_{G^{\prime}[V_{\geq 2}]}(v)$. Since there are exactly $2k+1$ lists of type
$(2)$, at least $\frac{1}{2k+1}$ fraction of $N_{G^{\prime}[V_{\geq 2}]}(v)$
has list of different type than $(2)$ or has list $\\{j-1,j+1\\}$. Thus for
the branch where we set $L(v)=\\{a\\}$, the sizes of lists of at least
$\frac{1}{2k+1}\cdot(\mu\log\mu)^{1/d}$ vertices decrease. In the branch where
we remove $a$ from $L(v)$, we decrease the size of $L(v)$ at least by one.
After both branches we apply the reduction rules, so the desired inequality
follows.

If we apply (B2) to $(G^{\prime},L^{\prime})$ – recall that we stop recursing
in this case – and if $d=k+2$, then

$F(\mu)\leq(2k+1)^{(\mu\log\mu)^{\frac{d-1}{d}}}\cdot p(n),$

since we guess the coloring on $N_{G^{\prime}[V_{\geq}2]}^{d-1}$ whose size is
bounded by $(\mu\log\mu)^{\frac{d-1}{d}}$ (in this case we could not apply
(B1) so the degrees in $G^{\prime}[V_{\geq 2}]$ are bounded by
$(\mu\log\mu)^{1/d}$) and the number of possible colors is at most $2k+1$.

In case of $d=k+3$, we have:

$F(\mu)\leq(2k+1)^{(2k+1)\cdot(\mu\log\mu)^{\frac{d-1}{d}}}\cdot p(n),$

where additional $(2k+1)$ in the exponent comes from the fact that we applied
(B2) possibly $(2k+1)$ times.

We can conclude that $F(\mu)\leq
2^{\mathcal{O}((\mu\log\mu)^{\frac{d-1}{d}})}$ (see for example [9], proof of
Theorem 7) which combined with the inequality $\mu\leq n$ completes the proof.
∎

In the following lemma we show that we can solve every instance corresponding
to a leaf of $\mathcal{R}$ in polynomial time.

######  Lemma 3.

Let $(G^{\prime},L^{\prime})$ be an instance of $\textsc{LHom}(C_{2k+1})$ such
that $\operatorname{diam}(G^{\prime})\geq k+3$ and let $C$ be a fixed
precolored $(2k+1)$-cycle. Assume that we applied algorithm Recursion Tree to
$(G^{\prime},L^{\prime})$ and let $\mathcal{R}$ be the resulting recursion
tree. Let $(G,L)$ be as instance corresponding to a leaf in $\mathcal{R}$.
Then $(G,L)$ can be solved in polynomial time.

We skip the technical proof of Lemma 3 for now and we prove Theorem 7.

###### of Theorem 7.

Let $(G,L)$ be an instance of $\textsc{LHom}(C_{2k+1})$ such that the diameter
of $G$ is at most $d\in\\{k+2,k+3\\}$. As in Theorem 1, first for every
$i\in[2k]_{0}$, we check in polynomial time whether there is a list
homomorphism $\varphi:(G,L)\to C_{2k+1}$ such that no vertex is mapped to $i$
– this can be done by [12]. If there is no such list homomorphism, we guess
$2k+1$ vertices $c_{0},\ldots,c_{2k}$ which will be colored so that $c_{i}$ is
mapped to $i$. We add the edges $c_{i}c_{i+1}$ and we obtain an induced
$(2k+1)$-cycle $C$ (if not, then we are dealing with a no-instance). Note that
adding edges cannot increase the diameter and since the edges are added
between vertices precolored with consecutive vertices, we obtain an equivalent
instance.

Now for $(G,L)$ and $C$ as the fixed precolored $(2k+1)$-cycle we use the
algorithm Recursion Tree, which by Lemma 2 in time
$2^{\mathcal{O}((n\log{n})^{\frac{d-1}{d}})}$ returns a tree $\mathcal{R}$.
Moreover, in order to solve the instance $(G,L)$ it is enough to solve every
instance corresponding to a leaf of $\mathcal{R}$ by Lemma 2, and by Lemma 3,
we can solve each such instance in polynomial time. Furthermore, since the
size of $\mathcal{R}$ is bounded by the running time, the instance $(G,L)$ can
be solved in time $2^{\mathcal{O}((n\log{n})^{\frac{d-1}{d}})}\cdot
n^{\mathcal{O}(1)}=2^{\mathcal{O}((n\log{n})^{\frac{d-1}{d}})}$, which
completes the proof. ∎

It only remains to show that any instance corresponding to a leaf in the
recursion tree can be solved in polynomial time. We first prove it for $d=k+2$
as a warm-up and then we prove that for more complicated case of $d=k+3$.

###### Proof of Lemma 3, case $d=k+2$.

First observe that for every vertex $u$ outside the cycle $C$, we have that
$L(u)\subseteq\\{i-2,i-1,i,i+1,i+2\\}$ for some $i\in[2k]_{0}$. Indeed, by 4,
there must be $i\in[2k]_{0}$ such that
$\operatorname{dist}(u,c_{i})=\operatorname{dist}(u,c_{i+1})$, and since the
reduction rules (R1) and (R2) cannot be applied and
$\operatorname{diam}(G)\leq k+2$, then that distance is either $k+1$ or $k+2$,
so 2 gives us the desired properties of $L(u)$. Moreover, since for the
branching rule (B2), if we could, we chose vertex $v$ whose distance from $C$
is at least $\lceil\frac{d}{2}\rceil=\lceil\frac{k+2}{2}\rceil$, each vertex
left is at distance $\lfloor\frac{k+2}{2}\rfloor$ from $C$. Indeed, every
vertex $u^{\prime}$ that was in $N^{\leq d}_{G[V\geq 2]}(v)$ has list of size
at most $2$. So for any vertex $u$ left in $V_{\geq 3}$, the shortest $u$-$v$
path (whose length is at most the diameter $d$) should contain a vertex from
$C$ and length of that path is at least
$\operatorname{dist}(v,C)+\operatorname{dist}(u,C)$. So either all vertices
outside $C$ were at distance at most $\lfloor\frac{k+2}{2}\rfloor$ or $v$ was
at distance at least $\lceil\frac{k+2}{2}\rceil$ and thus $u$ is at distance
at most $\lfloor\frac{k+2}{2}\rfloor$ from $C$. If $k>2$, then
$\lfloor\frac{k+2}{2}\rfloor<k$, which by 1 implies that $L(u)$ is an
independent set. Combining it with the fact that
$L(u)\subseteq\\{i-2,i-1,i,i+1,i+2\\}$ and $u\in V_{\geq 3}$, we obtain
$L(u)=\\{i-2,i,i+2\\}$. If $k=2$, then by 1, we obtain that $L(u)$ is of type
$(2,2)$, and this means that $L(u)=\\{j-2,j,j+2\\}$ for some $j\in[2k]_{0}$.

Therefore, in any case we obtain that if $|L(v)|\geq 3$, then
$L(v)=\\{i-2,i,i+2\\}$ for some $i\in[2k+1]_{0}$. Moreover, observe that if
$u$ is a neighbor of such $v$ and the reduction rule (R3) cannot be applied,
then the possible list of $u$ is $\\{i-1,i+1\\}$, $\\{i-3,i+1\\}$,
$\\{i-1,i+3\\}$, $\\{i-3,i-1,i+1\\}$, or $\\{i-1,i+1,i+3\\}$ (here we point
out that we already know the structure of lists of size $3$). If for some
vertex $v$ with list $\\{i-2,i,i+2\\}$ there is no $u\in N(v)$ with one of
lists $\\{i-1,i+1\\}$, $\\{i-3,i+1\\}$, $\\{i-1,i+3\\}$, then we add such a
vertex $u$ to $G$ and make it adjacent to $v$. Note that now the diameter of
$G$ might increase, but we will not care about the diameter anymore. Moreover,
any list homomorphism on $G-u$ can be extended to $u$, since each color on
$L(u)$ has a neighbor on the list of the neighbor of $u$.

So since now, we can assume that for a vertex $v$ with list $\\{i-2,i,i+2\\}$,
all lists $\\{i-1,i+1\\}$, $\\{i-3,i+1\\}$, $\\{i-1,i+3\\}$ are present on
$N(v)$.

Constructing BCSP instance. We construct an instance of BCSP as follows. We
start with $\operatorname{BCSP}(C_{2k+1},G-V_{3},L)$. First, for every vertex
$v\in V_{3}$ and for every $v^{\prime},v^{\prime\prime}\in V_{2}\cap N(v)$, we
leave in $C(v^{\prime},v^{\prime\prime})$ only such pairs that have a common
neighbor in $L(v)$. Furthermore, for every edge $uv$ with $u,v\in V_{3}$ and
lists $L(u)=\\{i-2,i,i+2\\}$, $L(v)=\\{i-1,i+1,i+3\\}$, and for every pair
$u^{\prime},v^{\prime}\in V_{2}$ such that $uu^{\prime},vv^{\prime}\in E(G)$,
we remove (if they are present) from $C(u^{\prime},v^{\prime})$ the following
pairs: $(i-3,i+2)$, $(i-1,i+4)$, and $(i+3,i-2)$. This completes the
construction of the instance $(V,L,C)$ of BCSP.

Clearly the instance $(V,L,C)$ is constructed in polynomial time. Moreover, by
Theorem 5, this instance can be solved in polynomial time.

Correctness. It remains to show that the instance $(G,L)$ is equivalent to the
instance $(V,L,C)$. First suppose that there is a list homomorphism
$\varphi:(G,L)\to C_{2k+1}$. Consider an assignment $f=\varphi|_{V_{1}\cup
V_{2}}$. We have to verify that $f$ satisfies all constraints of the instance
$(V,L,C)$. Clearly $f$ has to satisfy all constraints coming from
$\operatorname{BCSP}(C_{2k+1},G[V_{1}\cup V_{2}],L)$. Furthermore, since
$\varphi$ is a homomorphism on $G$, for every $v\in V_{3}$ and every pair
$v^{\prime},v^{\prime\prime}\in N(v)\cap V_{2}$, we have that $f(v^{\prime})$
and $f(v^{\prime\prime})$ must have a common neighbor in $L(v)$. Finally, we
have to verify that $f$ satisfies constraints that were introduced for edges
of $G[V_{3}]$. Suppose that there are $u^{\prime},v^{\prime}$ such that
$(f(u^{\prime}),f(v^{\prime}))$ was removed from $C(u^{\prime},v^{\prime})$
for an edge $uv$ of $G[V_{3}]$ such that $uu^{\prime},vv^{\prime}\in E(G)$.
Let $L(u)=\\{i-2,i,i+2\\}$ and $L(v)=\\{i-1,i+1,i+3\\}$. Suppose first that
$f(u^{\prime})=i-3$ and $f(v^{\prime})=i+2$. Since $\varphi$ is a list
homomorphism and $uu^{\prime}\in E(G)$, we must have $\varphi(u)=i-2$, and
since $uv\in E(G)$ we must have $\varphi(v)=i-1$. However, $i-1$ is non-
adjacent to $i+2$ and thus the edge $vv^{\prime}$ cannot be properly colored,
a contradiction. Now suppose that $f(u^{\prime})=i-1$ and $f(v^{\prime})=i+4$.
Similarly, we must have $\varphi(v)=i+3$ and $\varphi(u)\in\\{i-2,i\\}$ so the
edge $uv$ cannot be properly colored. Finally, suppose that
$f(u^{\prime})=i+3$ and $f(v^{\prime})=i-2$. Then we must have
$\varphi(u)=i+2$ and $\varphi(v)=i-1$ so again $uv$ cannot properly colored, a
contradiction. Therefore, $f$ satisfies all constraints.

Now suppose that there is a satisfying assignment $f:V\to V(H)$ of $(V,L,C)$.
Observe that if we consider $\varphi=f$ on $V_{1}\cup V_{2}$, then $\varphi$
is a list homomorphism on $G[V_{1}\cup V_{2}]$. It remains to show that
$\varphi$ can be extended to vertices of $V_{3}$. Consider a vertex $v\in
V_{3}$ with list $\\{i-2,i,i+2\\}$ for some $i\in[2k]_{0}$. Recall that $v$
has neighbors with lists $\\{i-3,i+1\\}$ and $\\{i-1,i+3\\}$. Since $f$
satisfies the constraints, the colors on $N(v)$ have a common neighbor in
$L(v)$. Furthermore, we claim that this common neighbor is unique. Indeed, if
the neighbor of $v$ with list $\\{i-3,i+1\\}$ is colored with $i-3$, then we
already know that $v$ has to be mapped to $i-2$. Otherwise, $v$ has to be
mapped to one of $i,i+2$. If the neighbor of $v$ with list $\\{i-1,i+3\\}$ is
mapped to $i+3$, then $v$ has to be mapped to $i+2$, otherwise, $v$ has to be
mapped to $i$. Therefore, we extend $\varphi$ to vertices of $V_{3}$ in the
only possible way. It remains to show that $\varphi$ respects the edges of
$V_{3}$. Suppose not and let $uv$ be an edge which is not properly colored.
Let $L(u)=\\{i-2,i,i+2\\}$ and $L(v)=\\{i-1,i+1,i+3\\}$. First suppose that
$\varphi(u)=i-2$ and $\varphi(v)\in\\{i+1,i+3\\}$. A neighbor of $u$ with list
$\\{i-3,i+1\\}$ has to be mapped to $i-3$ and a neighbor of $v$ with list
$\\{i-2,i+2\\}$ has to be mapped to $i+2$, but then the mapping $f$ does not
satisfy the constraints since we removed the pair $(i-3,i+2)$. So now suppose
that $u$ is mapped to $i$ and $v$ is mapped to $i+3$. Then a neighbor of $v$
with list $\\{i,i+4\\}$ is mapped to $i+4$ and a neighbor of $u$ with list
$\\{i-1,i+3\\}$ is mapped to $i-1$, but the pair $(i-1,i+4)$ was removed.
Finally suppose that $u$ is mapped to $i+2$ and $v$ is mapped to $i-1$. Then a
neighbor of $u$ with list $\\{i-1,i+3\\}$ is mapped to $i+3$ and a neighbor of
$v$ with list $\\{i-2,i+2\\}$ is mapped to $i-2$, which is a contradiction
because we removed the pair $(i+3,i-2)$. Therefore $\varphi$ is a list
homomorphism, which completes the proof. ∎

###### Proof of Lemma 3, case $d=k+3$.

First observe that for every vertex $v$ outside the cycle $C$, we have that
$L(v)\subseteq\\{i-3,i-2,i-1,i,i+1,i+2,i+3\\}$ for some $i\in[2k]_{0}$.
Indeed, there must be $i\in[2k]_{0}$ such that
$\operatorname{dist}(v,c_{i})=\operatorname{dist}(v,c_{i+1})$, and since the
reduction rules (R1) and (R2) cannot be applied and
$\operatorname{diam}(G)\leq k+3$, then that distance is either $k+1$, $k+2$,
or $k+3$, so 2 gives us the desired properties of $L(v)$.

As in the case of $d=k+2$, we can show that each vertex in $V_{\geq 3}$ is at
distance at most $\lfloor\frac{d}{2}\rfloor=\lfloor\frac{k+3}{2}\rfloor$ from
$C$. If $k>3$, then $\lfloor\frac{k+3}{2}\rfloor<k$, so $L(v)$ is an
idependent set and $L(v)$ is a subset of list of type $(1,1,\ldots,1)$. If
$k=2$, then again $L(v)=\\{i-2,i,i+2\\}$ and if $k=3$, then
$L(v)\subseteq\\{i-3,i-1,i+1,i+3\\}$.

Note that if $k=2$, then all list are of the same type as in the case for
$d=k+2$, so we can solve the instance in the same way in polynomial time. So
since now we can assume that $k\geq 3$. We also poin out that in case $k=3$,
if a list of size at least $3$ is not of type $(2,2,2)$, then it is of type
$(2,2)$.

Therefore if $v\in V_{\geq 3}$, then $L(v)$ is one of the following types:
$(2,2,2)$, $(2,2)$, $(2,4)$, $(4,2)$, $(2,3)$, $(3,2)$.

First observe that if a vertex $v$ has list $L(v)=\\{i-2,i,i+3\\}$ for some
$i\in[2k]_{0}$, then
$\operatorname{dist}(v,c_{k+i})=\operatorname{dist}(v,c_{k+i+1})=k+3$ or
$\operatorname{dist}(v,c_{k+i+1})=\operatorname{dist}(v,c_{k+i+2})=k+3$. In
both cases $\operatorname{dist}(v,c_{k+i+1})=k+3$. On the other hand, since
$L(v)$ contains vertices at odd distance ($i$ and $i+3$), then by 1, we must
have that $\operatorname{dist}(v,c_{k+i-1})=k-1$, which is a contradiction
with the fact that $\operatorname{dist}(c_{k+i+1},c_{k+i-1})=2$. Hence, we
cannot have a vertex with list of type $(2,3)$. The case of type $(3,2)$ is
symmetric.

Observe that list of types $(2,2,2)$, $(2,4)$, $(4,2)$ can only appear on
vertices $v$ such that there is $i\in[2k]_{0}$ and
$\operatorname{dist}(v,c_{i})=\operatorname{dist}(v,c_{i+1})=k+3$. We will
show that this cannot happen for every $i\in[2k]_{0}$.

######  Claim 7.1.

Let $v$ and $i$ be such that
$\operatorname{dist}(v,c_{i})=\operatorname{dist}(v,c_{i+1})=k+3$. Then there
is no $u$ such that
$\operatorname{dist}(u,c_{j})=\operatorname{dist}(u,c_{j+1})=k+3$ for
$j\in\\{i+k-2,i+k-1,\ldots,i+k+3\\}$.

Proof of Claim. Assume that there is $u$ and
$j\in\\{i+k-2,i+k-1,\ldots,i+k+3\\}$ such that
$\operatorname{dist}(u,c_{j})=\operatorname{dist}(u,c_{j+1})=k+3$. Since we
still have a vertex $v$ such that
$\operatorname{dist}(v,c_{i})=\operatorname{dist}(v,c_{i+1})=k+3$, there was a
vertex $v^{\prime}$ such that
$\operatorname{dist}(v,c_{i})=\operatorname{dist}(v,c_{i+1})=k+3$ for which we
applied (B2). Since $u$ is left after this application of (B2) the all
shortest $u$-$v^{\prime}$-paths contain a vertex of $C$. Since
$\operatorname{dist}(v^{\prime},c_{i})=\operatorname{dist}(v^{\prime},c_{i+1})=k+3$,
for any $\ell$ we have $\operatorname{dist}(v^{\prime},c_{i+\ell+1})\geq
k+3-\ell$ and $\operatorname{dist}(v^{\prime},c_{i-\ell})\geq k+3-\ell$.
Furthermore, we have $\operatorname{dist}(u,c_{j-\ell})\geq k+3-\ell$ and
$\operatorname{dist}(u,c_{j+1+\ell})\geq k+3-\ell$. On the other hand, for
some $r\in[2k]_{0}$, we must have
$\operatorname{dist}(v^{\prime},c_{r})+\operatorname{dist}(u,c_{r})\leq
d=k+3$. It can be verified that this cannot happen when
$j\in\\{i+k-2,i+k-1,\ldots,i+k+3\\}$.

Let $v$ be a vertex with list of one of types $(2,2,2)$, $(2,4)$, $(4,2)$,
$(2,3)$, $(3,2)$. Since the reduction rules cannot be applied, we can observe
the following.

  1. 1.

If $L(v)$ is of type $(2,2,2)$, i.e., $L(v)=\\{i-3,i-1,i+1,i+3\\}$ for some
$i\in[2k]_{0}$, then $v$ must have at least one neighbor with one of lists:
$\\{i-4,i-2,i,i+2\\}$, $\\{i-4,i-2,i+2\\}$, $\\{i-4,i,i+2\\}$. Similarly, $v$
must have at least one neighbor with one of lists: $\\{i-2,i,i+2,i+4\\}$,
$\\{i-2,i+2,i+4\\}$, $\\{i-2,i,i+4\\}$.

  2. 2.

If $L(v)$ is of type $(2,4)$, i.e., $L(v)=\\{i-2,i,i+4\\}$ for some
$i\in[2k]_{0}$, then $v$ must have at least one neighbor with one of lists:
$\\{i-3,i-1,i+1,i+3\\}$, $\\{i-3,i-1,i+3\\}$, $\\{i-3,i+1,i+3\\}$. Similarly,
$v$ must have at least one neighbor with one of lists:
$\\{i-1,i+1,i+3,i+5\\}$, $\\{i-1,i+1,i+5\\}$, $\\{i-1,i+3,i+5\\}$.

The case of type $(4,2)$ is symmetric to type $(2,4)$.

Therefore, for any vertex $v$ with list of one of types $(2,2,2)$, $(2,4)$,
$(4,2)$, and such that
$\operatorname{dist}(v,c_{j})=\operatorname{dist}(v,c_{j+1})=k+3$, there are
neighbors $u,w$ of $v$ such that
$\operatorname{dist}(u,c_{j-1})=\operatorname{dist}(u,c_{j})=k+3$ and
$\operatorname{dist}(w,c_{j+1})=\operatorname{dist}(v,c_{j+2})=k+3$. By the
claim, we know that there is $j\in[2k]_{0}$ such that there is no vertex $u$
such that $\operatorname{dist}(u,c_{j})=\operatorname{dist}(u,c_{j+1})=k+3$.
Thus, we can conclude that there are no vertices with lists of type $(2,2,2)$,
$(2,4)$, and $(4,2)$.

Therefore, all lists that are present in our instance, are the same as in the
proof for the case $d=k+2$. Thus we can solve the instance in polynomial time,
which completes the proof. ∎

##  6 Beyond odd cycles

In this section we consider target graphs other than odd cycles. Instead, we
focus on input graphs with diameter at most $2$. Since homomorphisms preserve
edges, for graphs $G,H$, a homomorphism $\varphi:G\to H$ and a sequence of
vertices $v_{1},\ldots,v_{k}$ forming a path in $G$, the sequence
$\varphi(v_{1}),\ldots,\varphi(v_{k})$ forms a walk in $H$. Therefore, if $G$
has diameter at most $2$, we can assume that the target graph $H$ has also
diameter at most $2$. The following observation is straightforward.

######  Observation 5.

Let $G,H$ be graphs such that $G$ is connected. If there exists a homomorphism
$\varphi:G\to H$, then the image $\varphi(V(G))$ induces in $H$ a subgraph
with diameter at most $\operatorname{diam}(G)$.

We prove the following stronger version of Theorem 4.

######  Theorem 8.

Let $H$ be a simple triangle-free graph. Then $\textsc{LHom}(H)$ is
polynomial-time solvable on diameter-$2$ graphs.

###### Proof.

Let $(G,L)$ be an instance of $\textsc{LHom}(H)$. We guess the set of colors
that will be used – by 5 they should induce a diameter-$2$ subgraph
$H^{\prime}$ of $H$. For each such $H^{\prime}$, we guess
$h^{\prime}=|H^{\prime}|$ vertices $v_{1},\ldots,v_{h^{\prime}}$ of $G$ that
will be injectively mapped to $V(H^{\prime})$. For each tuple
$(H^{\prime},v_{1},\ldots,v_{h^{\prime}})$, we solve the instance
$(G,L^{\prime})$ of $\textsc{LHom}(H^{\prime})$, where $L^{\prime}(v)=x_{i}$
for $v=v_{i}$, $i\in[h^{\prime}]$ and $L^{\prime}(v)=L(v)$ otherwise. Note
that $(G,L)$ is a yes-instance if and only if at least one instance
$(G,L^{\prime})$ is a yes-instance.

First for every edge $x_{i}x_{j}\in E(H^{\prime})$, if $v_{i},v_{j}$ are non-
adjacent, we add the edge $v_{i}v_{j}$ to $G$ – note that this operation is
safe, since we cannot increase the diameter by adding edges and we only add
edges between vertices that must be mapped to neighbors in $H^{\prime}$.
Therefore, we can assume that the set
$V^{\prime}=\\{v_{1},\ldots,v_{h^{\prime}}\\}$ induces a copy of $H^{\prime}$
in $G$ (if not, then we have an extra edge, which means that we are dealing
with a no-instance). Furthermore, we exhaustively apply reduction rules
(R3)–(R6).

So now assume that none of the reduction rules (R3)–(R6) can be applied.
Suppose there is $v\in V(G)\setminus V^{\prime}$ – if there is no such $v$,
then we can return YES as an answer. Moreover, we choose such $v$ which is
adjacent to some vertex of $V^{\prime}$ (see Fig. 1). Let us denote
$V(H)=\\{x_{1},\ldots,x_{h^{\prime}}\\}$ so that
$L^{\prime}(v_{i})=\\{x_{i}\\}$ for $i\in[h^{\prime}]$. Suppose that there
exists $\varphi:(G,L^{\prime})\to H^{\prime}$ and let $x_{i}=\varphi(v)$. Then
$v$ cannot be adjacent to $v_{i}$ since there are no loops in $H^{\prime}$.
Furthermore, the only neighbors of $v$ in $V^{\prime}$ can be the neighbors of
$v_{i}$. Suppose that there is $v_{j}\in N_{G}(v_{i})\cap V^{\prime}$ which is
non-adjacent to $v$. Since the diameter of $G$ is at most $2$, then there must
be $u\in N_{G}(v)\cap N_{G}(v_{j})$. Observe that $u\notin V^{\prime}$.
Indeed, $v$ does not have any neighbors in $V^{\prime}\setminus N_{G}(v_{i})$
and if $u\in N_{G}(v)$, then there is a triangle $uv_{i}v_{j}$ in a copy of
$H^{\prime}$, a contradiction. Furthermore, it must hold that $\varphi(u)$ is
adjacent to $x_{i}$ in $H^{\prime}$ as $u$ is adjacent to $v$ and
$\varphi(v)=x_{i}$, and similarly, $\varphi(u)$ must be adjacent to $x_{j}$ as
$u$ is adjacent to $v_{j}$. Then $\varphi(u)x_{i}x_{j}$ forms a triangle in
$H^{\prime}$, a contradiction. Thus $v$ must be adjacent to all vertices of
$N(v_{i})\cap V^{\prime}$.

$v_{i}$$v_{j}$$v$$u$$H^{\prime}$ Figure 1:  Copy of $H^{\prime}$ in $G$ and a
vertex $v$ such that for some homomorphism $\varphi$, it holds
$\varphi(v_{i})=\varphi(v)$. We show that a vertex $u$ which is a common
neighbor of $v$ and some neighbor $v_{j}$ of $v_{i}$ in the copy of
$H^{\prime}$ cannot exist.

Since (R3) cannot be applied, each vertex of $L^{\prime}(v)$ is adjacent to
all vertices of $N_{H}(x_{i})$. Moreover, since (R5) cannot be applied, we can
conclude that $L^{\prime}(v)=\\{x_{i}\\}$. Furthermore, since (R6) cannot be
applied, we must have $v=v_{i}\in V^{\prime}$, a contradiction. This completes
the proof. ∎

##  7 Lower bound

In this section we prove Theorem 3.

###### Proof of Theorem 3.

We reduce from $3$-SAT. Let $\phi$ be an instance with $n$ variables
$x_{1},\ldots,x_{n}$ and $m$ clauses $\gamma_{1},\ldots,\gamma_{m}$. We
construct $G$ as follows.

We start with a $(2k+1)$-cycle $C$ on vertices $\\{v_{0},\ldots,v_{2k}\\}$.
For every clause $\gamma_{j}$ we add a copy of $C_{2k+1}$ on vertices
$a_{j},b_{j},c^{1}_{j},c^{2}_{j},\ldots,c^{2k-1}_{j}$ and we add edges
$v_{1}a_{j},b_{j}v_{2}$. For every variable $x_{i}$, we add a copy of
$C_{2k+1}$ with vertices $x_{i}^{0},\ldots,x_{i}^{2k}$ and identify
$x_{i}^{0}$ with $v_{0}$.

For every clause $\gamma_{j}$, we fix ordering of its variables. Furthermore,
for every variable $x_{i}$ of $\gamma_{j}$ we add a path $P_{ij}$ as follows.

  1. 1.

If $x_{i}$ is the first variable of $\gamma_{j}$ we add a path $P_{ij}$ on
$2k+1$ vertices, identify its first vertex with $a_{j}$. Furthermore, for
$\ell=2,\ldots,2k$, we make the $\ell$-th vertex of the path adjacent to
$v_{\ell}$. Finally, if the occurence of $x_{i}$ in $C_{j}$ is positive, then
we identify the $(2k+1)$th vertex of the path with $x_{i}^{2k}$. Otherwise, we
identify the $(2k+1)$th vertex with $x_{i}^{1}$.

  2. 2.

If $x_{i}$ is the second variable of $\gamma_{j}$, then we add a path $P_{ij}$
on three vertices, identify the first vertex with $b_{j}$, and make the second
vertex adjacent to $v_{1}$. Finally, if the occurence of $x_{i}$ in $C_{j}$ is
positive we identify the third vertex of the path with $x_{i}^{1}$. Otherwise,
we identify it with $x_{i}^{2k}$.

  3. 3.

If $x_{i}$ is the third variable of $\gamma_{j}$, then we add a path $P_{ij}$
on $k+2$ vertices, identify the first one with $c^{k}_{j}$, and make the
$(k+1)$-th one adjacent to $v_{1}$. Finally, if the occurence of $x_{i}$ in
$C_{j}$ is positive, then we identify the last vertex of the path with
$x_{i}^{1}$, and otherwise, we identify it with $x_{i}^{2k}$.

This completes the construction of $G$ (see Fig. 2). Note that
$|V(G)|=\mathcal{O}(n+m)$. We first prove that $\phi$ is satisfiable if and
only if $G\to H$.

$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$a_{j}$$b_{j}$$c_{j}^{1}$$c_{j}^{2}$$c_{j}^{3}$$x_{2}^{1}$$x_{2}^{2}$$x_{2}^{3}$$x_{2}^{4}$$x_{1}^{1}$$x_{1}^{2}$$x_{1}^{3}$$x_{1}^{4}$$x_{3}^{1}$$x_{3}^{2}$$x_{3}^{3}$$x_{3}^{4}$
Figure 2:  Construction of $G$ for $k=2$ and clause $\gamma_{j}=(\neg
x_{1}\lor x_{2}\lor\neg x_{3})$. Green vertices belong to the cycle $C$, blue
vertices are those introduced for variables, and yellow ones are those
introduced for the clause $\gamma_{j}$. Remaining vertices belong to paths
$P_{ij}$.

######  Claim 8.1.

If $G\to C_{2k+1}$, then $\phi$ is satisfiable.

Proof of Claim 8.1: First suppose that there exists $\varphi:G\to C_{2k+1}$
and without loss of generality, assume that $\varphi(v_{i})=i$ for
$i\in[2k]_{0}$. Note that for every variable, there are exactly two ways of
coloring its corresponding copy of $C_{2k+1}$, i.e., one with
$\varphi(x_{i}^{2k})=2k$, and the other with $\varphi(x_{i}^{2k})=1$. We
define a truth assignment $\psi$ of the variables, so that $x_{i}$ is true if
and only if $\varphi(x_{i}^{2k})=2k$.

Let us verify that $\psi$ is a satisfying assignment of $\phi$. Consider a
clause $\gamma_{j}$ and its corresponding copy of $C_{2k+1}$. Observe that
$a_{j}$ is adjacent to vertex precolored with $1$ and $b_{j}$ is adjacent to a
vertex precolored with $2$. Therefore, the pair $(a_{j},b_{j})$ must be
colored in one of three ways: $(0,1),(2,3),(2,1)$. First assume that
$(a_{j},b_{j})$ is colored with $(0,1)$ and let $x_{i}$ be the first variable
of $C_{j}$. Recall that $P_{ij}$ is a path on $2k+1$ vertices with $a_{j}$ as
the first vertex. Moreover, for every $\ell=2,\ldots,2k$, the $\ell$th vertex
of $P_{ij}$ is adjacent to $v_{\ell}$ and we have $\varphi(v_{\ell})=\ell$.
Thus $\ell$th vertex of $P_{ij}$ has to be mapped to one of
$\\{\ell-1,\ell+1\\}$. Furthermore, $\varphi(a_{j})=0$, so the second vertex
of $P_{ij}$ has to be mapped to $1$. Then $\ell$th vertex has to be mapped to
$\ell-1$, and thus the last vertex has to be mapped to $2k$. Recall that the
last vertex of the path $P_{ij}$ is $x_{i}^{2k}$ if the occurence of $x_{i}$
is positive and $x_{i}^{1}$, otherwise. In both cases by the definition of the
truth assignment $\psi$, $x_{i}$ satisfies $C_{j}$.

Now assume that the pair $(a_{j},b_{j})$ is colored with $(2,3)$ and let
$x_{i}$ be the second variable of $C_{j}$. Then observe that the consecutive
vertices of $P_{ij}$ must be colored with $3,2,1$, respectively. Recall that
the last vertex of $P_{ij}$ is $x_{i}^{1}$ if the occurence of $x_{i}$ is
positive and $x_{i}^{2k}$, otherwise. In both cases by the definition of truth
assignment $\psi$, $x_{i}$ satisfies $C_{j}$.

Finally assume that the pair $(a_{j},b_{j})$ is colored with $(2,1)$ and let
$x_{i}$ be the third variable of $C_{j}$. Observe that in this case
$c_{j}^{k}$, which is also the first vertex of $P_{ij}$, must be colored with
$k+1$. Since the $(k+1)$th vertex of $P_{ij}$ is adjacent to $v_{1}$ colored
with $1$, it can be colored only with one of $0,2$. However, if it is colored
with $0$, then there must be a walk in $C_{2k+1}$ from $0$ to $k+1$ of length
exactly $k$, a contradiction. Therefore, the last vertex of $P_{ij}$ must be
colored with $1$. As in the previous cases, $x_{i}$ satisfies $C_{j}$.
$\lrcorner$

######  Claim 8.2.

If $\phi$ is satisfiable, then $G\to C_{2k+1}$.

Proof of Claim 8.2: Let $\psi$ be a truth assignment satisfying $\phi$. We
define $\varphi:G\to C_{2k+1}$ as follows. First, we set $\varphi(v_{i}):=i$.
Moreover, for every variable $x_{i}$, we extend $\varphi$ to the vertices of
the cycle introduced for $x_{i}$, so that $\varphi(x_{i}^{1})=1$ if
$\psi(x_{i})=1$, and $\varphi(x_{i}^{1})=2k$ otherwise. Furthermore, for each
clause $\gamma_{j}$ we fix one variable $x_{i}$ that satisfies $\gamma_{j}$ in
assignment $\psi$. Then, if the first variable satisfies $\gamma_{j}$, we
color $(a_{j},b_{j})$ with $(0,1)$, if it is the second variable, we color
$(a_{j},b_{j})$ with $(2,3)$, and if it is the third one, we color
$(a_{j},b_{j})$ with $(2,1)$. We extend $\varphi$ to the remaining vertices of
the cycle introduced for $\gamma_{j}$ in the only possible way.

Observe that so far, $\varphi$ respect all the edges. It remains to extend
$\varphi$ to vertices of paths $P_{ij}$. Consider such a path $P_{ij}$
introduced for a clause $\gamma_{j}$ and its variable $x_{i}$.

Case 1: $x_{i}$ is the first variable of $\gamma_{j}$. In this case $P_{ij}$
is a path on $2k+1$ vertices with $a_{j}$ as the first vertex and $x_{i}^{1}$
or $x_{i}^{2k}$ as the last vertex depending on the sign of the occurence of
$x_{i}$ in $\gamma_{j}$. Moreover, for $\ell=2,\ldots,2k$, $\ell$th vertex of
$P_{ij}$ is adjacent to $v_{\ell}$, so it has to be mapped to one of
$\ell-1,\ell+1$. If $a_{j}$ is colored with $2$, then $\varphi$ can be
extended to $P_{ij}$ so that the $2k$ consecutive vertices are mapped
respectively to $2,3,4\ldots,2k,0$. Now note that this respects all the edges
of $P_{ij}$ as the last vertex is colored either with $1$ or $2k$, both
adjacent to $0$. So now assume that $a_{j}$ is colored with $0$. By the
definition of $\varphi$, the variable $x_{i}$ must satisfy $\gamma_{j}$, and
thus the last vertex of $P_{ij}$ has to be mapped to $2k$. Then we can extend
$\varphi$ to $P_{ij}$ so that the consecutive vertices of $P_{ij}$ are mapped
respectively to $0,1,\ldots,2k$.

Case 2: $x_{i}$ is the second variable of $\gamma_{j}$. Then $P_{ij}$ is a
path on $3$ vertices with $b_{j}$ being the first vertex. Moreover, the second
vertex is adjacent to $v_{1}$, so it has to be mapped to $0$ or $2$. If
$b_{j}$ is mapped to $1$, then we set $\varphi$ on the second vertex of
$P_{ij}$ to $0$, which is adjacent to both $1,2k$, and thus $\varphi$ respects
the edges of $P_{ij}$. If $b_{j}$ is mapped to $3$, then the variable $x_{i}$
satisfies $\gamma_{j}$ and thus the last vertex of $P_{ij}$ has to be mapped
to $1$. Therefore we can set $\varphi$ on the second vertex of $P_{ij}$ to
$2$.

Case 3: $x_{i}$ is the third variable of $\gamma_{j}$. In this case $P_{ij}$
is a path on $k+2$ vertices with $c_{j}^{k}$ being the first vertex and
$(k+1)$th vertex adjacent to $v_{1}$. Note that if $(a_{j},b_{j})$ is mapped
to $(0,1)$, $(2,3)$, or $(2,1)$ , then $c_{j}^{k}$ is mapped respectively to
$k+1$, $k+3$, $k+2$. In the first case, we can extend $\varphi$ so that
consecutive $k+1$ vertices of $P_{ij}$ are mapped respectively to
$k+1,k+2,\ldots,2k,0$ and since the $k+1$th vertex is mapped to $0$ adjacent
to both $1,2k$, $\varphi$ respects all the edges of $P_{ij}.$ In the second
case we extend $\varphi$ to $P_{ij}$ so that consecutive $k+1$ vertices of
$P_{ij}$ are mapped respectively to $k+3,k+4,\ldots,2k,0,1,0$ and again
$\varphi$ respects the edges of $P_{ij}$. So let us consider the third case.
Recall that this happens when $x_{i}$ satisfies $C_{j}$ and thus the last
vertex of $P_{ij}$ is mapped to $1$. We extend $\varphi$ so that the
consecutive vertices of $P_{ij}$ are mapped respectively to
$k+2,k+1,k,\ldots,2,1$, which clearly respects the edges of $P_{ij}$. This
completes the proof of the claim. $\lrcorner$

Now we show that the radius (and thus the diameter) of $G$ is bounded.

######  Claim 8.3.

The radius of $G$ is at most $k+1$.

Proof of Claim 8.3: We show that each vertex is at distance at most $k+1$ from
$v_{1}$. It holds for every vertex of the cycle $C$ and every vertex that is
adjacent to $C$. The remaining vertices are those introduced for variables,
the vertices of cycles introduced for clauses, and those of paths $P_{ij}$
introduced for clauses and their third variables.

The vertices introduced for variables are at distance at most $k$ from
$v_{0}$, and thus at most $k+1$ from $v_{1}$. For a cycle introduced for a
clause $\gamma_{j}$, each its vertex is at distance at most $k$ from $a_{j}$,
which is adjacent to $v_{1}$. Finally, it remains to check the internal
vertices of the paths introduced in the third case. Recall that each such a
path consist of $k+2$ vertices ($k$ internal vertices) and the $(k+1)$-th
vertex is adjacent to $v_{1}$. This completes the proof of the claim.
$\lrcorner$

Therefore the $\textsc{Hom}(C_{2k+1})$ problem is NP-hard on diameter-$(2k+2)$
graphs. Moreover, since $|V(G)|=\mathcal{O}(n+m)$, there is no algorithm
solving $\textsc{Hom}(C_{2k+1})$ in time
$2^{o(|V(G)|)}\cdot|V(G)|^{\mathcal{O}(1)}$, unless the ETH fails. This
completes the proof. ∎

##  8 Conclusion

In this paper we studied the computational complexity of
$\textsc{Hom}(C_{2k+1})$ problem on bounded-diameter graphs. We proved that
for $k\geq 2$, the $\textsc{Hom}(C_{2k+1})$ problem can be solved in
polynomial-time on diameter-$(k+1)$ graphs and we gave subexponential-time
algorithms for diameter-$(k+2)$ and -$(k+3)$ graphs. We also proved that
$\textsc{Hom}(H)$ for triangle-free graph $H$, can be solved in polynomial
time on diameter-$2$ graphs.

The main open problem in this area remains the question whether $3$-Coloring
on diameter-$2$ graphs can be solved in polynomial time. However, as more
reachable, we propose the following future research directions. (i) Is the
$\textsc{Hom}(C_{2k+1})$ problem NP-hard for the subexponential-time cases,
i.e., diameter-$(k+2)$ or -$(k+3)$ graphs? (2) Let $H$ be a diameter-$2$ graph
such that $H$ contains a triangle but $H\not\to K_{3}$. Is the
$\textsc{Hom}(H)$ problem NP-hard?

Aknowledgements. We are grateful to Paweł Rzążewski for inspiring and fruitful
discussions.

## References

  * [1] Laurent Beaudou, Florent Foucaud, and Reza Naserasr.  Smallest c2(l)+1-critical graphs of odd-girth 2k+1.  Discret. Appl. Math., 319:564–575, 2022.
  * [2] Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma.  Independent feedback vertex sets for graphs of bounded diameter.  Inf. Process. Lett., 131:26–32, 2018.
  * [3] Christoph Brause, Petr A. Golovach, Barnaby Martin, Pascal Ochem, Daniël Paulusma, and Siani Smith.  Acyclic, star, and injective colouring: Bounding the diameter.  Electron. J. Comb., 29(2), 2022.
  * [4] Andrei A. Bulatov and Amirhossein Kazeminia.  Complexity classification of counting graph homomorphisms modulo a prime number.  In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1024–1037. ACM, 2022.
  * [5] Jin-Yi Cai and Ashwin Maran.  The complexity of counting planar graph homomorphisms of domain size 3.  In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 1285–1297. ACM, 2023.
  * [6] Victor A. Campos, Guilherme de C. M. Gomes, Allen Ibiapina, Raul Lopes, Ignasi Sau, and Ana Silva.  Coloring problems on bipartite graphs of small diameter.  Electron. J. Comb., 28(2):2, 2021.
  * [7] Rajesh Chitnis, László Egri, and Dániel Marx.  List h-coloring a graph by removing few vertices.  Algorithmica, 78(1):110–146, 2017.
  * [8] Radu Curticapean, Holger Dell, and Dániel Marx.  Homomorphisms are a good basis for counting small subgraphs.  In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 210–223. ACM, 2017.
  * [9] Michal Dębski, Marta Piecyk, and Paweł Rzążewski.  Faster 3-coloring of small-diameter graphs.  SIAM J. Discret. Math., 36(3):2205–2224, 2022.
  * [10] Oliver Ebsen and Mathias Schacht.  Homomorphism thresholds for odd cycles.  Comb., 40(1):39–62, 2020.
  * [11] Keith Edwards.  The complexity of colouring problems on dense graphs.  Theor. Comput. Sci., 43:337–343, 1986.
  * [12] Tomás Feder, Pavol Hell, and Jing Huang.  List homomorphisms and circular arc graphs.  Comb., 19(4):487–505, 1999.
  * [13] Tomás Feder, Pavol Hell, and Jing Huang.  Bi-arc graphs and the complexity of list homomorphisms.  J. Graph Theory, 42(1):61–80, 2003.
  * [14] Jacob Focke, Dániel Marx, and Paweł Rzążewski.  Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds.  In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 431–458. SIAM, 2022.
  * [15] Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa, and Kirill Simonov.  The fine-grained complexity of graph homomorphism parameterized by clique-width.  In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229 of LIPIcs, pages 66:1–66:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [16] A. M. H. Gerards.  Homomorphisms of graphs into odd cycles.  J. Graph Theory, 12(1):73–83, 1988.
  * [17] Carla Groenland, Isja Mannens, Jesper Nederlof, Marta Piecyk, and Paweł Rzążewski.  Towards tight bounds for the graph homomorphism problem parameterized by cutwidth via asymptotic rank parameters.  CoRR, abs/2312.03859, 2023.
  * [18] Pavol Hell and Jaroslav Nešetřil.  On the complexity of h-coloring.  Journal of Combinatorial Theory, Series B, 48(1):92–110, 1990.
  * [19] Tereza Klimosová and Vibha Sahlot.  3-coloring c${}_{\mbox{4}}$ or c${}_{\mbox{3}}$-free diameter two graphs.  In Pat Morin and Subhash Suri, editors, Algorithms and Data Structures - 18th International Symposium, WADS 2023, Montreal, QC, Canada, July 31 - August 2, 2023, Proceedings, volume 14079 of Lecture Notes in Computer Science, pages 547–560. Springer, 2023.
  * [20] Aleksej Dmitrievich Korshunov.  On the diameter of graphs.  Soviet Math, 12:302:305, 1971.
  * [21] Hong-Jian Lai.  Unique graph homomorphisms onto odd cycles, II.  J. Comb. Theory, Ser. B, 46(3):363–376, 1989.
  * [22] Barnaby Martin, Daniël Paulusma, and Siani Smith.  Colouring h-free graphs of bounded diameter.  In Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen, editors, 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, volume 138 of LIPIcs, pages 14:1–14:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [23] Barnaby Martin, Daniël Paulusma, and Siani Smith.  Colouring graphs of bounded diameter in the absence of small cycles.  Discret. Appl. Math., 314:150–161, 2022.
  * [24] George B. Mertzios and Paul G. Spirakis.  Algorithms and almost tight results for 3-colorability of small diameter graphs.  Algorithmica, 74(1):385–414, 2016.
  * [25] Karolina Okrasa, Marta Piecyk, and Paweł Rzążewski.  Full complexity classification of the list homomorphism problem for bounded-treewidth graphs.  In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 74:1–74:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [26] Karolina Okrasa and Paweł Rzążewski.  Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs.  SIAM J. Comput., 50(2):487–508, 2021.
  * [27] Christos H. Papadimitriou.  Computational complexity.  Addison-Wesley, 1994.
  * [28] Sebastian Schnettler.  A structured overview of 50 years of small-world research.  Soc. Networks, 31(3):165–178, 2009.
  * [29] Petra Sparl and Janez Zerovnik.  Homomorphisms of hexagonal graphs to odd cycles.  Discret. Math., 283(1-3):273–277, 2004.