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.