$C_2k+1$-coloring of bounded-diameter graphs
<|reference_start|>$C_2k+1$-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 $\varphi: V(G) \to V(H)$. Note that $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 $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 $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 $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 $Hom(H)$ is polynomial-time solvable on diameter-$2$ graphs.<|reference_end|>
@article{piecyk2024$c_{2k+1}$-coloring,
    title={$C_{2k+1}$-coloring of bounded-diameter graphs},
    author={Marta Piecyk},
    journal={arXiv preprint arXiv:2403.06694},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.06694},
    primaryClass={math.CO cs.CC}
}