\pdfoutput=1 \documentclass[11pt]{article} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage{amsmath,amssymb,amsthm,mathtools,booktabs,array} \usepackage{tikz} \usepackage{needspace} \usepackage[margin=1in]{geometry} \usepackage[colorlinks=true,linkcolor=blue,urlcolor=blue,citecolor=blue]{hyperref} \hypersetup{ pdftitle={Parameterised complexity of graph homomorphism to odd cycles}, pdfauthor={Jason Davies}, pdfsubject={Parameterised complexity and a Lean-checked List Colouring reduction}, pdfkeywords={graph homomorphism, odd cycle, treewidth, pathwidth, feedback vertex set, Lean} } \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \DeclareMathOperator{\tw}{tw} \DeclareMathOperator{\pw}{pw} \DeclareMathOperator{\fvs}{fvs} \newcommand{\XNLP}{\mathsf{XNLP}} \newcommand{\XALP}{\mathsf{XALP}} \newcommand{\W}[1]{\mathsf{W}[#1]} \newcommand{\Z}{\mathbb{Z}} \newcommand{\lean}[1]{\nolinkurl{#1}} \makeatletter\g@addto@macro\UrlBreaks{\do\_}\makeatother \emergencystretch=2em \title{Parameterised complexity of graph homomorphism to odd cycles} \author{Jason Davies\thanks{\href{mailto:jason@jasondavies.com}{\nolinkurl{jason@jasondavies.com}}}} \date{November 18, 2026} \begin{document} \maketitle \begin{abstract} A nonbipartite graph has an odd-cycle core precisely when it maps to its shortest odd cycle. Core recognition and homomorphism to an input odd cycle are both XNLP-complete for the width of a supplied path decomposition, XALP-complete for the width of a supplied tree decomposition, and W[SAT]-hard and in W[P] for feedback vertex number. Hardness persists on connected, 2-degenerate $N$-vertex sources of girth $\Omega(N^{1-\varepsilon})$ for any fixed $0<\varepsilon<1$. Our reduction encodes lists by cycles sharing an edge. On inputs with an edge it increases treewidth and feedback vertex number by exactly two. Lean~4 checks this structural transfer. For feedback \emph{edge} number $r$, we compute the exact circular chromatic number in $2^{O(r)}$ time up to polynomial factors, which gives the same upper bound for both decision problems. \end{abstract} \section{Introduction} Does a nonbipartite graph $G$ map to its shortest odd cycle $C_h$? Gerards studied this question for graph homomorphisms~\cite{gerards1988}. It is also a recognition problem. The \emph{core} of a finite graph is its smallest homomorphically equivalent subgraph, unique up to isomorphism. If $G\to C_h$, the inclusion $C_h\to G$ gives equivalence, and $C_h$ is a core because every endomorphism of an odd cycle is an automorphism (Lemma~\ref{lem:rigid}). Conversely, if the core is $C_\ell$ for some odd $\ell$, then $C_\ell\to G$ gives an odd closed walk containing an odd cycle, so $h\leq\ell$. Composing $C_h\to G\to C_\ell$ gives $\ell\leq h$ by the same argument in $C_\ell$. Thus $\ell=h$. Bipartite graphs have no odd-cycle core. \begin{theorem}\label{thm:main} Consider two decision problems on a finite simple undirected graph $G$. \begin{itemize} \item Does $G$ have an odd cycle as its core? \item Given also an odd $n\geq5$ in binary, does $G\to C_n$? \end{itemize} Each problem is XNLP-complete for the width of a supplied path decomposition, XALP-complete for the width of a supplied tree decomposition, and W[SAT]-hard and in W[P] for $\fvs(G)$. All three hardness bounds hold on connected, 2-degenerate graphs of girth $\Omega(|V(G)|^{1-\varepsilon})$ for every fixed $0<\varepsilon<1$. \end{theorem} Deleting edges leads to a different algorithm. If deleting $r$ edges leaves a forest, both problems are solvable in $2^{O(r)}$ time up to polynomial factors. In fact we can compute the exact circular chromatic number $\chi_c(G)$ within this bound (Theorem~\ref{thm:edge-alg}). For odd $h\geq3$, the test $G\to C_h$ is the circular-colouring threshold $\chi_c(G)\leq 2h/(h-1)$~\cite{zhu2001}. If $h$ is the odd girth of $G$, inclusion of $C_h$ gives the reverse inequality. Core recognition therefore tests equality in this lower bound. Corollary~\ref{cor:relative-girth} also gives polynomial time for both problems at girth $\Omega(N\log\log N/\log N)$. The hardness proofs encode List Colouring in the geometry of an odd cycle. All reference cycles share an ordered edge $AB$. Its image determines the coordinates in every copy. A path from an input vertex to a forbidden coordinate then excludes exactly that colour. Each forbidden occurrence gets its own copy and path. Deleting $A,B$ exposes a subdivision of the input graph with trees attached. Contracting selected paths instead gives the input graph joined to the edge $AB$. These two views of the same graph give matching upper and lower bounds. \begin{theorem}\label{thm:transfer} There is a polynomial-size, logspace reduction from List Colouring on a graph $F$ to $G\to C_n$, with $n$ odd and $n\geq5$, such that \[ \tw(G)\leq\max\{\tw(F)+2,3\},\qquad \pw(G)\leq\pw(F)+6,\qquad \fvs(G)\leq\fvs(F)+2. \] Supplied tree or path decompositions can be transformed within the same resource bounds. For every feedback vertex set $S$ of $F$, the construction specifies a feedback vertex set of $G$ of size $|S|+2$. If $F$ contains an edge, then the treewidth and feedback vertex number bounds are exact: $\tw(G)=\tw(F)+2$ and $\fvs(G)=\fvs(F)+2$. \end{theorem} Theorem~\ref{thm:main} also gives hardness for minimum width by forgetting the supplied decomposition. Amarilli asked whether bounding the treewidths of both input graphs makes homomorphism fixed-parameter tractable~\cite{amarilli2016}. Here the target always has treewidth and pathwidth two. Since XNLP-hardness implies W[$t$]-hardness for every fixed $t\geq1$~\cite[Lemma~2]{bgns2024}, the reduction gives W[1]-hardness for the maximum of the two treewidths even on these targets. \paragraph{Prior work and attribution.} In May 2025 Amarilli reported workshop reductions indicating W[1]-hardness for the parameter $\max\{\tw(G),\tw(H)\}$~\cite{amarilli2016}. Amarilli later clarified (personal communication) that the reduction from $k$-Clique produces a homomorphism instance $G\to H$ with source pathwidth $\pw(G)=k$ and target pathwidth $\pw(H)=2$. Thus the workshop reduction already gives W[1]-hardness for source pathwidth with a target of pathwidth two. Our reduction from List Colouring takes $H$ to be an odd cycle and yields the completeness results for supplied decompositions in Theorem~\ref{thm:main}. We use the XNLP-completeness of List Colouring for pathwidth~\cite[Theorem~15]{bgns2024} and its XALP-completeness for treewidth~\cite[Theorem~8]{bggpp2022}. For feedback vertex number, Bodlaender, Groenland and Pilipczuk obtained W[3]-hardness for List Colouring and W[SAT]-hardness for Binary CSP~\cite[Table~1]{bgp2023}. Their Binary CSP reduction certifies the truth of subformulas by propagating choices down a formula tree \cite[Lemmas~11 and~14]{bgp2023full}. In Theorem~\ref{thm:list-feedback} we express that propagation with colour lists and ordinary edges, strengthening the W[3] lower bound for List Colouring in~\cite[Corollary~34]{bgp2023full}. Piecyk and Rz\k{a}\.{z}ewski studied cutwidth and feedback vertex number for list homomorphism. Their conditional cutwidth bounds also apply to ordinary homomorphism for odd-cycle targets~\cite{pr2021}. For each fixed odd cycle our reduction transfers algorithms in the opposite direction, from ordinary homomorphism to List Colouring with a fixed palette (Remark~\ref{thm:fixed}). Carbonnel gives single-exponential-time, polynomial-space algorithms measured in the number of source vertices for target families excluding a topological minor, together with improved randomised bounds for fixed odd-cycle targets~\cite[Theorems~1 and~2]{carbonnel2026}. These bounds concern source order rather than the structural parameters studied here. Disequality and list gadgets for projective cores are developed by Okrasa and Rz\k{a}\.{z}ewski~\cite[preprint version, Lemma~17 and Proposition~19]{or2021}; their fixed-target width overhead may depend on the target. Kostochka, Ne\v{s}et\v{r}il and Smol\'ikov\'a prove NP-completeness of fixed-$H$ colouring on 2-degenerate sources for nonbipartite triangle-free $H$~\cite[Theorem~1.3]{kns2001}. Here the elimination of lists is uniform and polynomial-size, with additive structural overhead independent of the target length for all three parameters. The single-link reference copies provide the feedback vertex guarantee as well as connected sources of prescribed large girth. \section{Properties of odd cycles} \paragraph{Conventions.} All graphs are finite, simple, and undirected. Path length counts edges. A tree decomposition consists of a nonempty tree $T$ and bags $(B_t)_{t\in V(T)}$ covering the graph's vertices and edges, such that the bags containing any given vertex induce a connected subtree of $T$. Its width is $\max\{0,\max_t |B_t|-1\}$. A path decomposition has a path as its index tree. The parameters $\tw$ and $\pw$ are the minimum widths over tree and path decompositions, respectively. Thus the empty graph has width zero, witnessed by a single empty bag. A feedback vertex set is a set whose deletion leaves a forest, and $\fvs$ denotes its minimum cardinality. We identify $V(C_n)$ with $\Z/n\Z$, with consecutive residues adjacent. Throughout this section $n\geq3$ is odd. \begin{lemma}[Rigidity]\label{lem:rigid} Every homomorphism $f:C_n\to C_n$ has the form $f(x)=r+\varepsilon x$, where $r\in\Z/n\Z$ and $\varepsilon\in\{1,-1\}$. In particular, fixing the ordered edge $(0,1)$ fixes every vertex. \end{lemma} \begin{proof} Choose the integer increment $+1$ or $-1$ for each of the $n$ consecutive steps of the image walk. Their sum is a multiple of $n$, lies in $[-n,n]$, and is odd. It is therefore $n$ or $-n$, forcing all increments to have the same sign. \end{proof} \begin{lemma}[Inequality link]\label{lem:link} A path of length $n-2$ has a homomorphism to $C_n$ with endpoint images $x,y$ if and only if $x\ne y$. \end{lemma} \begin{proof} The possible integer displacements of a walk of that length are \[ -(n-2),\;-(n-4),\;\ldots,\;n-4,\;n-2. \] These $n-1$ integers give distinct residues modulo $n$: a difference is $2j$ with $0<|j||X|$, output one vertex with an empty list and an empty deletion set. Henceforth assume $k\leq |X|$. Take the tree edges and add a clique $S$ of $k$ selectors, each with list $X$. Join every literal vertex to every selector. A colouring of the clique chooses a set $U\subseteq X$ of exactly $k$ true variables. Assign the following \emph{active} colours to the tree vertices. \begin{itemize} \item an AND gate $u$ has one colour $a_u$; \item an OR gate $u$ has a colour $a_{u,v}$ for each child $v$; \item a leaf $\neg x$ has colour $x$. \end{itemize} All gate colours are distinct and disjoint from $X$. The list at the root contains only its active colours. At every other vertex $v$ add one \emph{inactive} colour, namely $a_u$ when its parent $u$ is an AND gate and $a_{u,v}$ when its parent is an OR gate. Fix the selector colours. At a leaf $\neg x$, the active choice is available precisely when $x\notin U$. On a tree edge $uv$ from parent to child, the only colour shared by the two lists is the child's inactive colour. Hence an active AND gate forces every child to be active, and an OR gate coloured $a_{u,v}$ forces child $v$ to be active. Induction from the leaves shows that every active vertex represents a true subformula. The root must be active, including when the formula consists of one literal. Conversely, start at the root of a true formula. At a required AND gate use its active colour and require every child. At a required OR gate choose a true child, use its corresponding colour, and require that child alone. Colour each required leaf $\neg x$ with $x$ and all unrequired vertices with their inactive colours. The required leaves avoid all selector colours; on each tree edge the parent uses the child's inactive colour exactly when it requires that child. This gives a proper list colouring. Deleting the selectors leaves the original formula tree. For a tree of $t$ nodes with $\ell$ leaves, the graph has $t+k$ vertices and $t-1+\binom{k}{2}+k\ell$ edges. Gate colours can be named by their node and child indices. Given the formula as a node table with parent pointers, counters and input scans enumerate the lists and edges in logarithmic space. The supplied deletion set has size $k$, so the minimum feedback vertex number is also bounded by the input weight. \end{proof} \paragraph{Transferring hardness to cycles.} Apply Theorem~\ref{thm:transfer} to the two published width lower bounds and to Theorem~\ref{thm:list-feedback}. The transformed decompositions have the claimed widths. The $k$ selector hubs and the two anchors give a supplied feedback set of size $k+2$. We may adjoin a single isolated vertex with a singleton list to ensure a nonempty input, extending a supplied decomposition by a singleton bag. Proposition~\ref{prop:amplify} gives the asserted girth restriction with the same feedback set and at most two more vertices per path bag. The resulting graph has a shortest cycle of odd length equal to the target length. By the equivalence in the introduction, discarding the target proves the same hardness for core recognition. These graphs have chromatic number three, by 2-degeneracy and the presence of an odd cycle. \subsection{Membership} We first bound the target length so that binary encoding does not increase the resources needed by the algorithms. \begin{lemma}[Capping the target length]\label{lem:cap} Let $m=|V(G)|$ and let $n\geq5$ be odd. If $n>m$, then $G\to C_n$ if and only if $G$ is bipartite. Setting $n'=\min\{n,2m+5\}$ preserves whether $G\to C_n$. The binary encoding of $n$ can be transformed to the unary encoding of $n'$ in logarithmic space, leaving $G$ unchanged. \end{lemma} \begin{proof} An odd closed walk of length $t$ in $C_n$ has an odd integer displacement that is a multiple of $n$, so $t\geq n$. A nonbipartite graph on $m$ vertices contains an odd cycle of length at most $m$, precluding a homomorphism to $C_n$ when $n>m$. Conversely, a bipartition maps to any edge of $C_n$. If the cap changes the target, both $n$ and $n'$ exceed $m$, so the preceding equivalence applies to both. The cap is odd and at least five. Scan the binary digits of $n$ with an accumulator saturated at $2m+5$; then emit its value in unary. The counter uses $O(\log(m+2))$ bits and the output has $O(m+1)$ symbols. Input validity, including oddness, can also be checked by scans. No source parameter or supplied decomposition changes. \end{proof} By Lemma~\ref{lem:cap}, first replace a binary target length by its linear-size cap. In the membership arguments below, $n$ denotes this capped length, so target vertices have $O(\log N)$-bit identifiers and all loops over the target take polynomial time. We first isolate the common correctness argument. A bag assignment is a map $a_t:B_t\to V(H)$ that preserves every graph edge with both endpoints in $B_t$. \begin{lemma}[Gluing bag assignments]\label{lem:bags} For a tree decomposition $(T,(B_t))$ of $G$, a homomorphism $G\to H$ exists if and only if there are bag assignments that agree on $B_s\cap B_t$ for every edge $st$ of $T$. \end{lemma} \begin{proof} A homomorphism restricts to such assignments. Conversely, if a vertex $v$ occurs in two bags, every bag on the unique path between them also contains $v$. Agreement across adjacent bags therefore gives a single image for $v$, independent of the chosen occurrence. Vertex coverage defines this map on all of $G$, and edge coverage makes it a homomorphism. \end{proof} \paragraph{Supplied width.} On a path, guess one bag assignment at a time and check its internal edges and agreement with the preceding bag. On a rooted tree, visit children in depth-first order. Save the parent assignment, bag index and next-child index on the auxiliary stack before descending, then restore them on return. Every sibling thus sees the same parent assignment. Lemma~\ref{lem:bags} proves correctness in both cases. At most two assignments occupy the work tape, using $O((w+1)\log N)$ bits for width $w$ and input length $N$. Each bag and tree edge requires only polynomially many input scans. This gives XNLP membership on paths and XALP membership on trees. Appendix~\ref{app:cert} gives the preliminary logspace certificate check. \paragraph{Feedback vertex number.} A parameterised problem is in W[P] if a nondeterministic Turing machine decides it in time $f(k)N^{O(1)}$ with at most $f(k)\log N$ nondeterministic steps~\cite[Chapter~3]{flumgrohe2006}. Let $k=\fvs(G)$. Compute a minimum feedback vertex set $S$ deterministically in time $f(k)N^{O(1)}$~\cite{cygan2015}. Guess an image in $\Z/n\Z$ for every vertex of $S$, using $k\lceil\log_2 n\rceil$ nondeterministic bits, and reject unless the guess preserves the edges inside $S$. The graph $G-S$ is a forest; root each of its trees. For a vertex $x$ of $G-S$ and a residue $a$, call $(x,a)$ \emph{feasible} if $a$ is adjacent in $C_n$ to the guessed image of every neighbour of $x$ in $S$, and every child $y$ of $x$ has a feasible pair $(y,b)$ with $b$ adjacent to $a$. Feasibility is computed from the leaves upwards in polynomial time, and the guess extends to a homomorphism exactly when every root has a feasible pair. This proves membership in W[P]. This membership result also follows from the Binary CSP upper bound~\cite[Theorem~2]{bgp2023}, since the standard encoding preserves the constraint graph. For both List Colouring and the input-cycle problem, the remaining feedback-number gap is between W[SAT]-hardness and W[P]-membership. \paragraph{Core recognition.} For the width algorithms, guess an odd $3\leq\ell\leq|V(G)|$ and verify $C_\ell\to G$ by guessing a closed walk of length $\ell$ in logarithmic space. Then check $G\to C_\ell$ with the corresponding bag algorithm. For W[P], reject bipartite graphs and compute the odd girth deterministically in polynomial time before guessing the feedback-set images. The odd girth is the minimum distance between the two copies of any one vertex in the bipartite double cover, since this is the minimum length of an odd closed walk. This completes the proof of Theorem~\ref{thm:main}. \begin{remark}[Fixed target]\label{thm:fixed} For fixed odd $q\geq5$, enumerating all assignments on a supplied feedback set of size $s$ takes $O^*(q^s)$ time, where $O^*$ suppresses polynomial factors. Conversely, an $O^*(b^s)$ algorithm for $C_q$ yields the same bound for List Colouring on $q$ colours. At $n=q$ the decision equivalence holds for arbitrary lists, and the supplied set grows by two, costing a factor $b^2$ for fixed $b>1$. This transfer is unconditional. \end{remark} \begin{remark}[Forest targets] If a target forest has an edge, its sources are exactly the bipartite graphs. A nonempty edgeless target accepts precisely edgeless sources, and an empty target accepts only the empty source. Thus at target treewidth one the problem is polynomial-time decidable. \end{remark} \section{Circular colouring by feedback edge number}\label{sec:edge-alg} For $p\geq2q\geq2$, the circular clique $K_{p/q}$ has vertex set $\Z/p\Z$. Two colours are adjacent when their difference lies in the integer interval $[q,p-q]$ modulo $p$. Thus $K_{(2k+1)/k}$ is isomorphic to $C_{2k+1}$, since its two steps are $\pm k$ and $k$ is coprime to $2k+1$. Write $N=|V(G)|$ and $r=|E(G)|-N+c$, where $c$ is the number of connected components. This \emph{feedback edge number} counts the edges outside a spanning forest. \begin{theorem}\label{thm:edge-alg} For positive $p,q$ given in binary with $p\geq2q$, deciding $G\to K_{p/q}$ takes $2^{O(r)}|I|^{O(1)}$ time and polynomial space, where $|I|$ is the input length. The exact circular chromatic number of $G$ can be computed within the same bounds. \end{theorem} \begin{proof} On an oriented chain of $L$ edges, every step contributes an arbitrary integer in $[q,p-q]$. The possible sums are all integers in \[ [Lq,L(p-q)]. \] Indeed, start each step at $q$ and distribute any desired excess of at most $L(p-2q)$ among the steps. Reduction modulo $p$ gives exactly the feasible endpoint differences. In particular a component that is a cycle of length $L$ is feasible if and only if this interval contains a multiple of $p$. Repeatedly remove vertices of degree at most one. Any colouring extends back across these deletions, since every target colour has a neighbour. Test pure cycle components as above. In each other remaining component, suppress the maximal degree-two chains, retaining their lengths and any resulting loops or parallel edges. The multigraph has minimum degree three and its original feedback edge number $r_i$. With $b$ vertices and $e$ edges it satisfies $3b\leq2e$ and $e=b+r_i-1$, hence $e\leq3(r_i-1)$. Altogether there are at most $3r$ chains. For a chain directed from $u$ to $v$, put $w=L(p-2q)$ and let $a\in[0,p-1]$ represent $Lq\bmod p$. If $w\geq p-1$ every residue is possible. Otherwise, using representatives $0\leq x_vr$, within the same copy. Its vertex parent follows the same rule, except that the root's vertex parent is $h_v$. Emit the input bags with $A,B$ added, and the reference bags $\{A,B,x,\operatorname{parent}(x)\}$. These formulas require only coordinate comparisons and give the decomposition of $J$ directly. A required direct domain edge belongs to its copy's root bag when $d\geq2$, and to its owning input bag when $d=0$ or $d=1$. An original edge belongs to its owning input bag. Emit each subdivision chain of size-three bags from Section~\ref{sec:treewidth} at that bag. Parents within a chain are consecutive indices, so both bags and decomposition edges can be emitted without a general forest traversal. \paragraph{Emitting a path decomposition.} Implement the two stages of Section~\ref{sec:pathwidth} in order. For each input bag, emit its enlargement by $A,B$, followed by the reference windows for vertices whose first occurrence is that bag. Order these windows by vertex, residue, and reference position. This is an explicit stream of bags for $J$. For each required link, find the first bag of this stream containing its endpoints by regenerating the stream. At that bag insert the link's consecutive internal-vertex windows, retaining the whole bag of $J$. Order links with the same owning bag by their identifiers. The intermediate stream need not be stored: its bags and their contents can be recomputed by counters and input scans. If the input decomposition has $b$ bags, either construction uses $O(b+mn^2+(e+f)n)$ output bags. Every bag is emitted one vertex at a time, and each owning-bag query stores only indices and membership flags. The enumerations have a fixed number of nested loops over polynomially bounded ranges. Consequently the transducer uses $O(\log N)$ workspace, polynomial time, and polynomial output length, independently of the input width. \paragraph{Checking the certificate.} The algorithms do not assume valid decompositions as a promise. We encode a tree by a designated root and one parent pointer for every other bag. Reject out-of-range pointers and require every bag to reach the root within $b$ steps, where $b$ is the number of bags. This checks that the index graph is a tree using counters and rescans. For each graph vertex $v$, count its occurrence bags, say $a_v$, and the tree edges with both endpoints among those bags, say $e_v$. The induced index subgraph is a forest, so it is nonempty and connected exactly when $a_v>0$ and $e_v=a_v-1$. Thus these counts check vertex coverage and connected occurrences. Bag entries, duplicate entries, bag sizes, and coverage of each graph edge are checked by scans. For a path, check that every occurrence set is a nonempty interval. These preliminary checks take logarithmic workspace and polynomial time. No decomposition-finding algorithm is assumed. \section{Lean verification}\label{app:lean} The artifact uses Lean~4.35.0~\cite{deMouraUllrich2021} and mathlib v4.35.0~\cite{mathlib2020}. It checks the weighted-formula and List Colouring decision reductions, the supplied decomposition and feedback-set transfers, their numerical bounds and matching lower bounds, and the connection with odd-cycle cores. It also checks the original source girth and size bounds, the endpoint projection for odd subdivision, and the walk interval for an odd-cycle target. The circular-clique generalisation, graph-level girth amplification, encodings and running times are proved in the manuscript. To reproduce the audit at revision \texttt{848545a}, run \texttt{python3 scripts/check\_formalization.py} from the repository root~\cite{artifact}. It builds the library, checks for proof admissions and audits the principal declarations. \texttt{FORMALIZATION.md} indexes the statements and the README gives commands for the finite checks. Mathematical development, formalisation and drafting used AI assistance under human direction. \begin{thebibliography}{10} \raggedright \bibitem{adf1995} K. A. Abrahamson, R. G. Downey and M. R. Fellows. Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues. \emph{Annals of Pure and Applied Logic} 73(3):235--276, 1995. \href{https://doi.org/10.1016/0168-0072(94)00034-Z}{doi:10.1016/0168-0072(94)00034-Z}. \bibitem{amarilli2016} Antoine Amarilli. Complexity of the homomorphism problem parameterized by treewidth. \emph{Theoretical Computer Science Stack Exchange}, question~34877, June~2, 2016, with a \href{https://cstheory.stackexchange.com/questions/34877/#comment124806_34877}{comment on workshop reductions, May~30, 2025}. \url{https://cstheory.stackexchange.com/q/34877}. \bibitem{bggpp2022} Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk and Micha{\l} Pilipczuk. On the complexity of problems on tree-structured graphs. In \emph{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, LIPIcs, vol.~249, pp.~6:1--6:17. Schloss Dagstuhl, 2022. \href{https://doi.org/10.4230/LIPIcs.IPEC.2022.6}{doi:10.4230/LIPIcs.IPEC.2022.6}. \bibitem{bgns2024} Hans L. Bodlaender, Carla Groenland, Jesper Nederlof and C\'eline Swennenhuis. Parameterized problems complete for nondeterministic FPT time and logarithmic space. \emph{Information and Computation} 300:105195, 2024. \href{https://doi.org/10.1016/j.ic.2024.105195}{doi:10.1016/j.ic.2024.105195}. \bibitem{bgp2023} Hans L. Bodlaender, Carla Groenland and Micha{\l} Pilipczuk. Parameterized complexity of Binary CSP: vertex cover, treedepth, and related parameters. In \emph{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, LIPIcs, vol.~261, pp.~27:1--27:20. Schloss Dagstuhl, 2023. \href{https://doi.org/10.4230/LIPIcs.ICALP.2023.27}{doi:10.4230/LIPIcs.ICALP.2023.27}. \bibitem{bgp2023full} Hans L. Bodlaender, Carla Groenland and Micha{\l} Pilipczuk. Parameterized complexity of Binary CSP: vertex cover, treedepth, and related parameters. Full version, \href{https://arxiv.org/abs/2208.12543v5}{arXiv:2208.12543v5}, 2023. \bibitem{carbonnel2026} Cl\'ement Carbonnel. Faster algorithms for graph homomorphism via tractable constraint satisfaction. \href{https://arxiv.org/abs/2602.23000v2}{arXiv:2602.23000v2}, 2026. \bibitem{cygan2015} Marek Cygan, Fedor V. Fomin, {\L}ukasz Kowalik, Daniel Lokshtanov, D\'aniel Marx, Marcin Pilipczuk, Micha{\l} Pilipczuk and Saket Saurabh. \emph{Parameterized Algorithms}. Springer, 2015. \href{https://doi.org/10.1007/978-3-319-21275-3}{doi:10.1007/978-3-319-21275-3}. \bibitem{artifact} Jason Davies. Odd-cycle homomorphism: Lean formalisation and executable checks. Software repository, 2026. Version \href{https://github.com/jasondavies/odd-cycle-homomorphism/tree/848545ac03da8691fdd511e29b3e247e446fb523}{\texttt{848545a}}. \url{https://github.com/jasondavies/odd-cycle-homomorphism}. \bibitem{bs2002} B\'ela Bollob\'as and Endre Szemer\'edi. Girth of sparse graphs. \emph{Journal of Graph Theory} 39(3):194--200, 2002. \href{https://doi.org/10.1002/jgt.10023}{doi:10.1002/jgt.10023}. \bibitem{deMouraUllrich2021} Leonardo de Moura and Sebastian Ullrich. The Lean~4 theorem prover and programming language. In \emph{Automated Deduction -- CADE~28}, LNCS, vol.~12699, pp.~625--635. Springer, 2021. \href{https://doi.org/10.1007/978-3-030-79876-5_37}{doi:10.1007/978-3-030-79876-5\_37}. \bibitem{flumgrohe2006} J\"org Flum and Martin Grohe. \emph{Parameterized Complexity Theory}. Texts in Theoretical Computer Science. Springer, 2006. \href{https://doi.org/10.1007/3-540-29953-X}{doi:10.1007/3-540-29953-X}. \bibitem{gerards1988} A. M. H. Gerards. Homomorphisms of graphs into odd cycles. \emph{Journal of Graph Theory} 12(1):73--83, 1988. \href{https://doi.org/10.1002/jgt.3190120108}{doi:10.1002/jgt.3190120108}. \bibitem{ht2014} Hossein Hajiabolhassan and Ali Taherkhani. On the circular chromatic number of graph powers. \emph{Journal of Graph Theory} 75(1):48--58, 2014. \href{https://doi.org/10.1002/jgt.21722}{doi:10.1002/jgt.21722}. \bibitem{kns2001} A. Kostochka, J. Ne\v{s}et\v{r}il and P. Smol\'ikov\'a. Colorings and homomorphisms of degenerate and bounded degree graphs. \emph{Discrete Mathematics} 233:257--276, 2001. \href{https://doi.org/10.1016/S0012-365X(00)00245-4}{doi:10.1016/S0012-365X(00)00245-4}. \bibitem{longnote} Jason Davies. Homomorphisms to long odd cycles in time exponential in the order-to-length ratio. Companion manuscript, 2026. Distributed alongside this paper as \texttt{long-odd-cycles.pdf}. \bibitem{mathlib2020} The mathlib Community. The Lean mathematical library. In \emph{Certified Programs and Proofs (CPP 2020)}, pp.~367--381. ACM, 2020. \href{https://doi.org/10.1145/3372885.3373824}{doi:10.1145/3372885.3373824}. \bibitem{or2021} Karolina Okrasa and Pawe{\l} Rz\k{a}\.{z}ewski. Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs. \emph{SIAM Journal on Computing} 50(2):487--508, 2021. \href{https://doi.org/10.1137/20M1320146}{doi:10.1137/20M1320146}. Preprint version: \href{https://arxiv.org/abs/1906.08371v3}{arXiv:1906.08371v3}, 2020. \bibitem{pr2021} Marta Piecyk and Pawe{\l} Rz\k{a}\.{z}ewski. Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth. In \emph{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, LIPIcs, vol.~187, pp.~56:1--56:17. Schloss Dagstuhl, 2021. \href{https://doi.org/10.4230/LIPIcs.STACS.2021.56}{doi:10.4230/LIPIcs.STACS.2021.56}. \bibitem{vince1988} Andrew Vince. Star chromatic number. \emph{Journal of Graph Theory} 12(4):551--559, 1988. \href{https://doi.org/10.1002/jgt.3190120411}{doi:10.1002/jgt.3190120411}. \bibitem{zhu2001} Xuding Zhu. Circular chromatic number: a survey. \emph{Discrete Mathematics} 229(1--3):371--410, 2001. \href{https://doi.org/10.1016/S0012-365X(00)00217-X}{doi:10.1016/S0012-365X(00)00217-X}. \end{thebibliography} \end{document}