C₂ₖ₊₁-coloring of bounded-diameter graphs

For a fixed graph H, in the graph homomorphism problem, denoted by $Hom(H)$, we are given a graph G and we have to determine whether there exists an edge-preserving mapping φ: V(G) → V(H). Note that Hom(C₃), where C₃ 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 Hom(C₂ₖ₊₁) problem on bounded-diameter graphs for k≥ 2, so we consider all other odd cycles than C₃. We prove that for k≥ 2, the Hom(C₂ₖ₊₁) 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 Hom(C₂ₖ₊₁) 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 $Hom(H)$ is polynomial-time solvable on diameter-$2$ graphs.