betaFeedback

WorksComputer Science

Parameterised complexity of graph homomorphism to odd cycles

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 NN-vertex sources of girth Ω(N1−ε)\Omega(N^{1-\varepsilon}) for any fixed 0<ε<10<\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 edge number rr, we compute the exact circular chromatic number in 2O(r)2^{O(r)} time up to polynomial factors, which gives the same upper bound for both decision problems.

Introduction

Does a nonbipartite graph GG map to its shortest odd cycle ChC_h? Gerards studied this question for graph homomorphisms [13]. It is also a recognition problem. The core of a finite graph is its smallest homomorphically equivalent subgraph, unique up to isomorphism. If G→ChG \to C_h, the inclusion Ch→GC_h \to G gives equivalence, and ChC_h is a core because every endomorphism of an odd cycle is an automorphism (Lemma 3). Conversely, if the core is CℓC_\ell for some odd ℓ\ell, then Cℓ→GC_\ell\to G gives an odd closed walk containing an odd cycle, so h≤ℓh \le\ell. Composing Ch→G→CℓC_h \to G \to C_\ell gives ℓ≤h\ell\le h by the same argument in CℓC_\ell. Thus ℓ=h\ell= h. Bipartite graphs have no odd-cycle core.

Theorem 1. Consider two decision problems on a finite simple undirected graph GG.

  • Does GG have an odd cycle as its core?

  • Given also an odd n≥5n \ge5 in binary, does G→CnG \to C_n?

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)\operatorname{fvs}(G). All three hardness bounds hold on connected, 2-degenerate graphs of girth Ω(∣V(G)∣1−ε)\Omega(|V(G)|^{1-\varepsilon}) for every fixed 0<ε<10 < \varepsilon< 1.

Deleting edges leads to a different algorithm. If deleting rr edges leaves a forest, both problems are solvable in 2O(r)2^{O(r)} time up to polynomial factors. In fact we can compute the exact circular chromatic number χc(G)\chi_c(G) within this bound (Theorem 15). For odd h≥3h \ge3, the test G→ChG \to C_h is the circular-colouring threshold χc(G)≤2hh−1\chi_c(G) \le\frac{2h}{h-1} [21]. If hh is the odd girth of GG, inclusion of ChC_h gives the reverse inequality. Core recognition therefore tests equality in this lower bound. Corollary 17 also gives polynomial time for both problems at girth Ω(Nlog⁡log⁡N/log⁡N)\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 ABAB. 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 AA, BB exposes a subdivision of the input graph with trees attached. Contracting selected paths instead gives the input graph joined to the edge ABAB. These two views of the same graph give matching upper and lower bounds.

Theorem 2. There is a polynomial-size, logspace reduction from List Colouring on a graph FF to G→CnG \to C_n, with nn odd and n≥5n \ge5, such that

tw⁡(G)≤max⁡{tw⁡(F)+2,3},pw⁡(G)≤pw⁡(F)+6,fvs⁡(G)≤fvs⁡(F)+2.\operatorname{tw}(G) \le\max\{\operatorname{tw}(F) + 2, 3\}, \qquad\operatorname{pw}(G) \le\operatorname{pw}(F) + 6, \qquad\operatorname{fvs}(G) \le\operatorname{fvs}(F) + 2.

Supplied tree or path decompositions can be transformed within the same resource bounds. For every feedback vertex set SS of FF, the construction specifies a feedback vertex set of GG of size ∣S∣+2|S| + 2. If FF contains an edge, then the treewidth and feedback vertex number bounds are exact: tw⁡(G)=tw⁡(F)+2\operatorname{tw}(G) = \operatorname{tw}(F) + 2 and fvs⁡(G)=fvs⁡(F)+2\operatorname{fvs}(G) = \operatorname{fvs}(F) + 2.

Theorem 1 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 [2]. Here the target always has treewidth and pathwidth two. Since XNLP-hardness implies W[tt]-hardness for every fixed t≥1t \ge1 [4 Lemma 2], the reduction gives W[1]-hardness for the maximum of the two treewidths even on these targets.

Prior work and attribution. In May 2025 Amarilli reported workshop reductions indicating W[1]-hardness for the parameter max⁡{tw⁡(G),tw⁡(H)}\max\{\operatorname{tw}(G), \operatorname{tw}(H)\} [2]. Amarilli later clarified (personal communication) that the reduction from kk-Clique produces a homomorphism instance G→HG \to H with source pathwidth pw⁡(G)=k\operatorname{pw}(G) = k and target pathwidth pw⁡(H)=2\operatorname{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 HH to be an odd cycle and yields the completeness results for supplied decompositions in Theorem 1.

We use the XNLP-completeness of List Colouring for pathwidth [4 Theorem 15] and its XALP-completeness for treewidth [3 Theorem 8]. For feedback vertex number, Bodlaender, Groenland and Pilipczuk obtained W[3]-hardness for List Colouring and W[SAT]-hardness for Binary CSP [5 Table 1]. Their Binary CSP reduction certifies the truth of subformulas by propagating choices down a formula tree [6 Lemmas 11 and 14]. In Theorem 10 we express that propagation with colour lists and ordinary edges, strengthening the W[3] lower bound for List Colouring in [6 Corollary 34].

Piecyk and Rzążewski studied cutwidth and feedback vertex number for list homomorphism. Their conditional cutwidth bounds also apply to ordinary homomorphism for odd-cycle targets [19]. For each fixed odd cycle our reduction transfers algorithms in the opposite direction, from ordinary homomorphism to List Colouring with a fixed palette (Remark 13). 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 [7 Theorems 1 and 2]. 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ążewski [18 preprint version, Lemma 17 and Proposition 19]; their fixed-target width overhead may depend on the target. Kostochka, Nešetřil and Smolíková prove NP-completeness of fixed-HH colouring on 2-degenerate sources for nonbipartite triangle-free HH [15 Theorem 1.3]. 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.

Properties of odd cycles

Conventions. All graphs are finite, simple, and undirected. Path length counts edges. A tree decomposition consists of a nonempty tree TT and bags (Bt)t∈V(T)(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 TT. Its width is max⁡{0,max⁡t∣Bt∣−1}\max\{0,\max_t |B_t|-1\}. A path decomposition has a path as its index tree. The parameters tw⁡\operatorname{tw} and pw⁡\operatorname{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⁡\operatorname{fvs} denotes its minimum cardinality.

We identify V(Cn)V(C_n) with Z/nZ\mathbb{Z}/n\mathbb{Z}, with consecutive residues adjacent. Throughout this section n≥3n \ge3 is odd.

Lemma 3 (Rigidity). Every homomorphism f:Cn→Cnf:C_n\to C_n has the form f(x)=r+εxf(x)=r+\varepsilon x, where r∈Z/nZr\in\mathbb{Z}/n\mathbb{Z} and ε∈{1,−1}\varepsilon\in\{1,-1\}. In particular, fixing the ordered edge (0,1)(0,1) fixes every vertex.

Proof. Choose the integer increment +1+1 or −1-1 for each of the nn consecutive steps of the image walk. Their sum is a multiple of nn, lies in [−n,n][-n,n], and is odd. It is therefore nn or −n-n, forcing all increments to have the same sign. □\square

Lemma 4 (Inequality link). A path of length n−2n-2 has a homomorphism to CnC_n with endpoint images x,yx,y if and only if x≠yx\ne y.

Proof. The possible integer displacements of a walk of that length are

−(n−2),  −(n−4),  …,  n−4,  n−2.-(n-2),\;-(n-4),\;\ldots,\;n-4,\;n-2.

These n−1n-1 integers give distinct residues modulo nn: a difference is 2j2j with 0<∣j∣<n0<|j|<n, and nn is odd. None is zero modulo nn, since each is odd and has absolute value less than nn. Thus they give exactly the nonzero residues, and every listed displacement is realised by an appropriate sequence of forward and backward steps. □\square

A link below means a path of length n−2n-2 whose internal vertices are private. Different links may share endpoints, but no internal vertices.

The reduction

An instance of List Colouring consists of a graph FF and lists L(v)⊆{0,…,q−1}L(v)\subseteq\{0,\ldots,q-1\}. It asks for a map cc with c(v)∈L(v)c(v)\in L(v) for every vertex and c(u)≠c(v)c(u)\ne c(v) for every edge uvuv. Relabelling the palette is harmless. Choose the least odd integer n≥max⁡{5,q+1,∣V(F)∣}n\ge\max\{5,q+1,|V(F)|\}, and regard the lists as subsets of Z/nZ\mathbb{Z}/n\mathbb{Z}.

Construct GG as follows.

  1. Introduce a vertex hvh_v for every v∈V(F)v\in V(F) and two further vertices A,BA,B, with edge ABAB.

  2. For every pair (v,d)∈V(F)×Z/nZ(v,d)\in V(F)\times\mathbb{Z}/n\mathbb{Z}, introduce a copy Rv,dR_{v,d} of CnC_n, identifying its coordinates 0,10,1 with A,BA,B, respectively. All other vertices of these cycles are private.

  1. If d∉L(v)d \notin L(v), add a link from coordinate dd of Rv,dR_{v,d} to hvh_v. This is the only link belonging to that reference copy.

  1. For every edge uv∈E(F)uv \in E(F), add one link from huh_u to hvh_v.

There are no other edges. In particular, original edges of FF become links, not edges of GG. Copies Rv,dR_{v,d} with d∈L(v)d \in L(v) have no domain link; retaining these harmless copies makes the finite vertex type in Lean uniform.

In Figure 1, take L(v)={0,1}L(v)=\{0,1\} and L(u)={1,2}L(u)=\{1,2\}. The link from coordinate 22 allows image 00 at hvh_v via the walk 2,3,4,02,3,4,0. It excludes image 22 because C5C_5 has no closed walk of length three. The other domain links enforce the remaining exclusions, and the link between the hubs requires different colours.

Part of the construction for target $C_5$

Figure 1. Part of the construction for target C5C_5. Solid edges form two reference cycles sharing ABAB. After normalising A,BA,B to 0,10,1, their private vertices have the indicated images. Each dashed link has three edges and two private internal vertices; it forces its endpoint images to differ. The remaining reference copies and domain links are omitted.

Lemma 5. The instance (F,L)(F,L) is list-colourable if and only if G→CnG \to C_n.

Proof. Given a homomorphism, compose it with a target automorphism to place A,BA,B at 0,10,1. By Lemma 3, every reference cycle then maps coordinatewise to CnC_n. Lemma 4 says that the domain links exclude exactly the residues outside L(v)L(v) from the image of hvh_v. The links corresponding to edges of FF force adjacent vertices to have different images. Thus v↦f(hv)v \mapsto f(h_v) is a list colouring. Conversely, given a list colouring, map each hvh_v to its colour and every reference cycle coordinatewise. Each link has distinct endpoint images, so Lemma 4 extends the map over it. Private interiors make these extensions independent.

Treewidth

Deleting A,BA,B from GG exposes a subdivision of FF, trees attached at single hubs, and separate tree components. Subdivision preserves treewidth, and adding these trees raises it to at most max⁡{tw⁡(F),1}\max\{\operatorname{tw}(F),1\}, giving tw⁡(G−{A,B})≤max⁡{tw⁡(F),1}\operatorname{tw}(G-\{A,B\}) \le\max\{\operatorname{tw}(F),1\}. Adding the two anchors yields tw⁡(G)≤max⁡{tw⁡(F)+2,3}\operatorname{tw}(G) \le\max\{\operatorname{tw}(F)+2,3\}. We give an explicit certificate construction so the same bound holds for supplied decompositions within the claimed resources.

Let JJ contain the reference cycles, the hubs with the original edges of FF, and a direct edge from coordinate dd of Rv,dR_{v,d} to hvh_v for every pair (v,d)(v,d), including allowed colours. Root the private reference path 2,…,n−12,\ldots,n-1 at coordinate dd when d≥2d \ge2, and at coordinate 22 otherwise. Attach this root to hvh_v, allowing an extra edge when needed. The resulting graph of hubs and private paths contains J−{A,B}J-\{A,B\} and is obtained from FF by attaching rooted trees at single vertices.

Keep the input bags. For each new vertex xx, add the bag {x,parent⁡(x)}\{x,\operatorname{parent}(x)\} below its parent’s bag, attaching a root bag to an input bag containing its hub. These are bags of size at most two. Add A,BA,B to every bag. The resulting decomposition of JJ has width at most max⁡{w+2,3}\max\{w+2,3\}: old bags have size at most w+3w+3, and new bags have size at most four.

Delete unused direct domain edges and replace each required domain or original edge abab by its link. Subdivision uses bags of size three: for internal vertices x1,…,xtx_1,\ldots,x_t, attach the chain {b,a,x1},{b,x1,x2},…,{b,xt−1,xt}\{b,a,x_1\},\{b,x_1,x_2\},\ldots,\{b,x_{t-1},x_t\} at a bag containing a,ba,b. Vertex occurrences stay connected and all edges are covered. The width remains at most max⁡{w+2,3}\max\{w+2,3\}.

Pathwidth

Use the same auxiliary graph JJ as in § 3.1. Its direct domain edges for allowed colours can only help provide a decomposition for the eventual source.

Given a path decomposition of FF of width pp, add A,BA,B to every bag. At the first bag containing hvh_v, process all its reference cycles serially, retaining that enlarged bag. Traverse each reference cycle using a window of two consecutive private vertices. Every direct domain edge is covered when its reference vertex is in the window, since hvh_v is retained. This gives a path decomposition of JJ of width at most p+4p+4.

When the endpoints of an edge share a bag, subdividing that edge into an arbitrarily long path raises pathwidth by at most two: retain that bag and sweep the new path, with at most two consecutive internal vertices present at once. Process all subdivisions serially at their owning bags. Delete the unused direct domain edges and subdivide the required domain and original edges into links. Vertex intervals and edge coverage are preserved, giving pw⁡(G)≤p+6\operatorname{pw}(G) \le p+6. This conservative bound is the one formalised in Lean.

Feedback vertex sets

Let SS be a feedback vertex set of FF. Delete

S′={hv:v∈S}∪{A,B}S'=\{h_v:v\in S\}\cup\{A,B\}

from GG. The original-edge links form a subdivision of F−SF-S, together with pendant or detached path fragments from edges incident with SS. This is a forest. Every reference cycle minus A,BA,B is a path. Its single optional domain link attaches it to at most one surviving hub, or leaves pendant or detached fragments when an endpoint was deleted. Such attachments cannot create a cycle. Thus S′S' is a feedback vertex set and ∣S′∣=∣S∣+2|S'|=|S|+2.

Exact parameter transfer

Proposition 6. For the padded construction, K2∨FK_2 \vee F is a minor of GG, where the join adds two adjacent vertices adjacent to every vertex of FF. If FF contains an edge, then

tw⁡(G)=tw⁡(F)+2,fvs⁡(G)=fvs⁡(F)+2.\operatorname{tw}(G)=\operatorname{tw}(F)+2,\qquad\operatorname{fvs}(G)=\operatorname{fvs}(F)+2.

For every nonempty FF, also pw⁡(F)+2≤pw⁡(G)≤pw⁡(F)+6\operatorname{pw}(F)+2\le\operatorname{pw}(G)\le\operatorname{pw}(F)+6.

Proof. Since q<nq<n, residue n−1n-1 is forbidden at every hub. For each vv, take the copy Rv,n−1R_{v,n-1} and contract its entire private path and domain link into hvh_v. Its edges to coordinates 0 and 1 become hvAh_vA and hvBh_vB. These private paths and link interiors are disjoint for distinct hubs. Retain ABAB, contract the original-edge links to edges, and discard the unused pieces. This produces K2∨FK_2 \vee F without identifying hubs.

For nonempty FF, the standard join identity gives tw⁡(K2∨F)=tw⁡(F)+2\operatorname{tw}(K_2 \vee F)=\operatorname{tw}(F)+2. Every chordal completion of the join restricts to one of FF, and every chordal completion of FF extends to the join; adjoining the two universal vertices increases the maximum clique size by two. Minor monotonicity supplies the lower bound, and the upper bound in § 3.1 matches it when FF has an edge.

Write k=fvs⁡(F)k=\operatorname{fvs}(F), c=vc⁡(F)c=\operatorname{vc}(F) for its vertex cover number, and m=∣V(F)∣m=|V(F)|. Deleting both, exactly one, or neither of the two new vertices gives, respectively,

fvs⁡(K2∨F)=min⁡{k+2,c+1,m}.\operatorname{fvs}(K_2 \vee F)=\min\{k+2,c+1,m\}.

Indeed, with one new vertex surviving, the remaining vertices of FF must be independent; with both surviving, no vertex of FF may survive. When FF has an edge, k≤c−1k\le c-1: retain one vertex of a minimum vertex cover, leaving a star and isolated vertices after deleting the others. Also k≤m−2k\le m-2, by retaining the endpoints of an edge. Thus the displayed minimum is k+2k+2. Feedback vertex number is minor-monotone, so the existing upper bound fvs⁡(G)≤k+2\operatorname{fvs}(G)\le k+2 is exact.

Finally, pw⁡(K2∨F)=pw⁡(F)+2\operatorname{pw}(K_2 \vee F)=\operatorname{pw}(F)+2 for nonempty FF. Indeed, restricting any path decomposition of the join to FF gives a bag with at least pw⁡(F)+1\operatorname{pw}(F)+1 input vertices. Their occurrence intervals and those of the two universal vertices pairwise intersect. By the Helly property for intervals, some bag contains all these vertices, giving the lower bound. Adding the universal vertices to every input bag gives equality. Minor monotonicity and § 3.2 now give the bounds for GG. □

The minor argument uses a common missing colour, supplied by palette padding. The upper bounds also cover edgeless and empty inputs.

Size and construction resources

Write m=∣V(F)∣m=|V(F)|, e=∣E(F)∣e=|E(F)|, and f=∑v(n−∣L(v)∣)f=\sum_v(n-|L(v)|). The exact source size is

∣V(G)∣=m+2+mn(n−2)+(e+f)(n−3)≤2+m+mn2+(mn+m2)n.(1)|V(G)|=m+2+mn(n-2)+(e+f)(n-3)\le2+m+mn^2+(mn+m^2)n. \tag*{(1)}

Since n=O(q+m+1)n=O(q+m+1), the output size is polynomial in the explicit input size. Here the palette may be taken to contain only colours occurring in the lists: order the distinct labels by first occurrence in the input and replace each by its rank. Repeated scans compute these ranks in logarithmic space, so qq is bounded by the input length even if the original labels are large binary integers.

Vertices and bags are named by a constant number of polynomially bounded indices. Each gadget is processed at the first input bag covering its attachment, found by rescanning the input. In the path construction the intermediate bag stream can likewise be regenerated on demand. Appendix § 6 gives the enumeration and its bag counts. The transducer uses logarithmic workspace and polynomial time, completing the proof of Theorem 2.

Sparse sources and large girth

Proposition 7. The source GG is 2-degenerate. If FF is nonempty, its girth is exactly nn.

Proof. Repeatedly remove internal vertices of links, all of which have degree at most two in the remaining graph. Then remove the private reference vertices, again of degree at most two. Only ABAB and isolated hubs remain. This gives a degeneracy ordering.

Before adding links, the nontrivial component consists of nn-cycles sharing only the edge ABAB; its shortest cycle has length nn. Every link joins different components of this base graph, so a cycle using a link must use at least two links. Their private interiors force it to traverse each link in full, giving length at least 2(n−2)≥n2(n-2) \ge n. A reference cycle of length nn exists whenever FF has a vertex.

The choice m≤nm \le n gives a quantitative girth bound. By (1), ∣V(G)∣≤2+n+n3+2n3≤4n3|V(G)| \le2+n+n^3+2n^3 \le4n^3 for n≥5n \ge5. Thus for every nonempty input the girth is at least (∣V(G)∣/4)1/3(|V(G)|/4)^{1/3}. To impose any additional fixed lower bound on the girth, include it in the maximum defining nn. The target length remains polynomial in the input size, and all width and feedback bounds continue to hold.

The output is also connected. Since n≥q+1n \ge q+1, residue qq is outside every input list. Each hub therefore has a domain link to the reference component containing ABAB. Every remaining vertex lies in a reference copy or a link. For empty FF, the output is simply ABAB. This explains the strict palette padding in the choice of nn.

Amplifying the girth by odd subdivision

Write St(G)S_t(G) for the graph obtained by replacing each edge of GG by a path of tt edges with private internal vertices. The following equivalence also follows from the circular-colouring theory of odd subdivisions [14]. We give an explicit projection because the reduction changes both the source and the target.

Lemma 8. For odd n≥3n \ge3 and positive odd tt,

St(G)→Ctn⟺G→Cn.S_t(G) \to C_{tn} \Longleftrightarrow G \to C_n.

Proof. Given G→CnG \to C_n, send an original vertex of colour ii to titi in CtnC_{tn}. Consecutive colours in CnC_n give endpoints of a tt-edge arc in CtnC_{tn}. Map each replacement path along this arc.

Conversely, define a map from the residues modulo tntn to those modulo nn by writing an integer lift as qt+rqt+r, 0≤r<t0 \le r < t, and putting

π(qt+r)=q+(r mod 2)(modn).\pi(qt+r)=q+(r \bmod2)\pmod n.

Changing the lift by tntn changes qq by nn. The endpoints of a tt-step walk have lifts at odd distance d≤td \le t. Order these lifts increasingly. If they are in the same block of length tt, their remainders have opposite parities and their images differ by one. If they lie in successive blocks, their remainders differ by d−td-t, which is even. Now the block indices differ by one, so again the images are adjacent. Applying π\pi to the images of the original vertices of GG proves the reverse implication.

Proposition 9. For every fixed 0<ε<10<\varepsilon<1, the reduction on nonempty inputs can output a connected, 22-degenerate graph of order NN and girth Ω(N1−ε)\Omega(N^{1-\varepsilon}). Its shortest cycle has odd length equal to the new target length. Subdivision preserves the feedback vertex number and treewidth of the reduction graph and adds at most two to the width of its supplied path decomposition.

Proof. Let M=∣V(G)∣M=|V(G)| before subdivision. Fix an integer a≥1a \ge1 with a/(a+1)≥1−εa/(a+1) \ge1-\varepsilon, and set t=2Ma+1t=2M^a+1. Each cycle traverses its replacement paths in full, so subdivision multiplies every cycle length by tt. Proposition 7 thus gives girth tntn, witnessed by an odd cycle. A 22-degenerate graph has at most 2M2M edges, whence

N=M+(t−1)∣E(G)∣≤2tM=O(Ma+1),tn≥t=Ω(Na/(a+1)).N=M+(t-1)|E(G)|\le2tM=O(M^{a+1}), \qquad tn\ge t=\Omega(N^{a/(a+1)}).

The new graph is connected. Remove the new degree-two vertices first, then the original vertices, which are now isolated. This gives a 2-degeneracy ordering.

Every original feedback vertex set still hits every cycle. Conversely, replace each selected internal vertex by an endpoint of its original edge. Every original cycle lifts to a cycle and is hit by the resulting set. Contracting the replacement paths recovers GG as a minor. For the treewidth upper bound, attach a chain of bags of size three for each subdivided edge as in § 3.1. Here GG contains a cycle and hence has treewidth at least two. For pathwidth, retain the first bag containing the two endpoints and sweep the replacement paths assigned to that bag one at a time, keeping at most two internal vertices at once. For fixed aa, counters for edges, bags and positions along a path all use logarithmic space, and the output has polynomial length. Lemma 8 transfers the decision equivalence.

Complexity consequences

XNLP consists of problems decidable nondeterministically in time f(k)NO(1)f(k)N^{O(1)} and space f(k)log⁡Nf(k)\log N, where NN is the input length. XALP permits, in addition, an auxiliary stack with access only to its top; it has an equivalent characterisation by alternation with bounded total computation-tree size [4, 3]. We use parameterised logspace reductions, with workspace f(k)+O(log⁡N)f(k)+O(\log N).

List Colouring with a feedback vertex set

Theorem 10. List Colouring is W[SAT]-hard parameterised by feedback vertex number, even when the input includes a set of kk vertices whose deletion leaves a tree and the parameter is kk.

Proof. Weighted Antimonotone Satisfiability asks whether an AND/OR formula with leaves ¬x\neg x, for xx in a set XX of variables, is satisfied by setting exactly kk variables true. It is W[SAT]-complete [1 Theorem 4.1(ii)]. Use its formula tree, with a separate vertex for every literal occurrence, including repeated occurrences of the same variable. For k>∣X∣k>|X|, output one vertex with an empty list and an empty deletion set. Henceforth assume k≤∣X∣k\le|X|.

Take the tree edges and add a clique SS of kk selectors, each with list XX. Join every literal vertex to every selector. A colouring of the clique chooses a set U⊆XU\subseteq X of exactly kk true variables. Assign the following active colours to the tree vertices.

  • an AND gate uu has one colour aua_u;

  • an OR gate uu has a colour au,va_{u,v} for each child vv;

  • a leaf ¬x\neg x has colour xx.

All gate colours are distinct and disjoint from XX. The list at the root contains only its active colours. At every other vertex vv add one inactive colour, namely aua_u when its parent uu is an AND gate and au,va_{u,v} when its parent is an OR gate.

Fix the selector colours. At a leaf ¬x\neg x, the active choice is available precisely when x∉Ux\notin U. On a tree edge uvuv 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 au,va_{u,v} forces child vv 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 ¬x\neg x with xx 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 tt nodes with ℓ\ell leaves, the graph has t+kt+k vertices and t−1+(k2)+kℓ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 kk, so the minimum feedback vertex number is also bounded by the input weight. □

Transferring hardness to cycles. Apply Theorem 2 to the two published width lower bounds and to Theorem 10. The transformed decompositions have the claimed widths. The kk selector hubs and the two anchors give a supplied feedback set of size k+2k+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 9 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.

Membership

We first bound the target length so that binary encoding does not increase the resources needed by the algorithms.

Lemma 11 (Capping the target length). Let m=∣V(G)∣m=|V(G)| and let n≥5n \ge5 be odd. If n>mn>m, then G→CnG \to C_n if and only if GG is bipartite. Setting n′=min⁡{n,2m+5}n'=\min\{n,2m+5\} preserves whether G→CnG \to C_n. The binary encoding of nn can be transformed to the unary encoding of n′n' in logarithmic space, leaving GG unchanged.

Proof. An odd closed walk of length tt in CnC_n has an odd integer displacement that is a multiple of nn, so t≥nt \ge n. A nonbipartite graph on mm vertices contains an odd cycle of length at most mm, precluding a homomorphism to CnC_n when n>mn>m. Conversely, a bipartition maps to any edge of CnC_n.

If the cap changes the target, both nn and n′n' exceed mm, so the preceding equivalence applies to both. The cap is odd and at least five. Scan the binary digits of nn with an accumulator saturated at 2m+52m+5; then emit its value in unary. The counter uses O(log⁡(m+2))O(\log(m+2)) bits and the output has O(m+1)O(m+1) symbols. Input validity, including oddness, can also be checked by scans. No source parameter or supplied decomposition changes. □

By Lemma 11, first replace a binary target length by its linear-size cap. In the membership arguments below, nn denotes this capped length, so target vertices have O(log⁡N)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 at:Bt→V(H)a_t:B_t \to V(H) that preserves every graph edge with both endpoints in BtB_t.

Lemma 12 (Gluing bag assignments). For a tree decomposition (T,(Bt))(T,(B_t)) of GG, a homomorphism G→HG \to H exists if and only if there are bag assignments that agree on Bs∩BtB_s \cap B_t for every edge stst of TT.

Proof. A homomorphism restricts to such assignments. Conversely, if a vertex vv occurs in two bags, every bag on the unique path between them also contains vv. Agreement across adjacent bags therefore gives a single image for vv, independent of the chosen occurrence. Vertex coverage defines this map on all of GG, and edge coverage makes it a homomorphism. □

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 12 proves correctness in both cases. At most two assignments occupy the work tape, using O((w+1)log⁡N)O((w+1)\log N) bits for width ww and input length NN. Each bag and tree edge requires only polynomially many input scans. This gives XNLP membership on paths and XALP membership on trees. Appendix § 6 gives the preliminary logspace certificate check.

Feedback vertex number. A parameterised problem is in W[P] if a nondeterministic Turing machine decides it in time f(k)NO(1)f(k)N^{O(1)} with at most f(k)log⁡Nf(k)\log N nondeterministic steps [12 Chapter 3]. Let k=fvs⁡(G)k=\operatorname{fvs}(G). Compute a minimum feedback vertex set SS deterministically in time f(k)NO(1)f(k)N^{O(1)} [8]. Guess an image in Z/nZ\mathbb{Z}/n\mathbb{Z} for every vertex of SS, using k⌈log⁡2n⌉k\lceil\log_2 n\rceil nondeterministic bits, and reject unless the guess preserves the edges inside SS. The graph G−SG-S is a forest; root each of its trees. For a vertex xx of G−SG-S and a residue aa, call (x,a)(x,a) feasible if aa is adjacent in CnC_n to the guessed image of every neighbour of xx in SS, and every child yy of xx has a feasible pair (y,b)(y,b) with bb adjacent to aa. 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 [5 Theorem 2], 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.

Core recognition. For the width algorithms, guess an odd 3≤ℓ≤∣V(G)∣3\le\ell\le|V(G)| and verify Cℓ→GC_\ell\to G by guessing a closed walk of length ℓ\ell in logarithmic space. Then check G→Cℓ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 1.

Remark 13 (Fixed target). For fixed odd q≥5q\ge5, enumerating all assignments on a supplied feedback set of size ss takes O∗(qs)O^*(q^s) time, where O∗O^* suppresses polynomial factors. Conversely, an O∗(bs)O^*(b^s) algorithm for CqC_q yields the same bound for List Colouring on qq colours. At n=qn=q the decision equivalence holds for arbitrary lists, and the supplied set grows by two, costing a factor b2b^2 for fixed b>1b>1. This transfer is unconditional.

Remark 14 (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.

Circular colouring by feedback edge number

For p≥2q≥2p\ge2q\ge2, the circular clique Kp/qK_{p/q} has vertex set Z/pZ\mathbb{Z}/p\mathbb{Z}. Two colours are adjacent when their difference lies in the integer interval [q,p−q][q,p-q] modulo pp. Thus K(2k+1)/kK_{(2k+1)/k} is isomorphic to C2k+1C_{2k+1}, since its two steps are ±k\pm k and kk is coprime to 2k+12k+1. Write N=∣V(G)∣N=|V(G)| and r=∣E(G)∣−N+cr=|E(G)|-N+c, where cc is the number of connected components. This feedback edge number counts the edges outside a spanning forest.

Theorem 15. For positive p,qp,q given in binary with p≥2qp\ge2q, deciding G→Kp/qG\to K_{p/q} takes 2O(r)∣I∣O(1)2^{O(r)}|I|^{O(1)} time and polynomial space, where ∣I∣|I| is the input length. The exact circular chromatic number of GG can be computed within the same bounds.

Proof. On an oriented chain of LL edges, every step contributes an arbitrary integer in [q,p−q][q,p-q]. The possible sums are all integers in

[Lq,L(p−q)].[Lq,L(p-q)].

Indeed, start each step at qq and distribute any desired excess of at most L(p−2q)L(p-2q) among the steps. Reduction modulo pp gives exactly the feasible endpoint differences. In particular a component that is a cycle of length LL is feasible if and only if this interval contains a multiple of pp.

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 rir_i. With bb vertices and ee edges it satisfies 3b≤2e3b \le2e and e=b+ri−1e=b+r_i-1, hence e≤3(ri−1)e \le3(r_i-1). Altogether there are at most 3r3r chains.

For a chain directed from uu to vv, put w=L(p−2q)w=L(p-2q) and let a∈[0,p−1]a \in[0,p-1] represent LqLq mod pp. If w≥p−1w \ge p-1 every residue is possible. Otherwise, using representatives 0≤xv<p0 \le x_v < p, the permitted integer differences xv−xux_v-x_u form the nonempty intersections

[1−p,p−1]∩[a+jp,a+w+jp],j∈{−2,−1,0}.[1-p,p-1] \cap[a+jp,a+w+jp], \qquad j \in\{-2,-1,0\}.

For a loop the difference is zero. Enumerate one interval per constrained chain. Each chosen interval [A,B][A,B] gives two difference constraints xv−xu≤Bx_v-x_u \le B and xu−xv≤−Ax_u-x_v \le-A. Express the coordinate bounds relative to a common variable, which may be translated to zero. A branch is feasible exactly when the constraint digraph has no negative cycle. In that case shortest distances from a new source of zero-weight arcs give integral coordinates. The chain criterion extends the endpoint colours independently across their private interiors. Conversely any colouring selects a feasible branch. The 33r3^{3r} branches can be processed sequentially. All weights, including L(p−q)L(p-q), have polynomial bit length.

For a graph with an edge, χc(G)\chi_c(G) is the least feasible ratio p/qp/q. Vince’s finite-attainment theorem gives a minimiser with p≤Np \le N for connected graphs [20 Theorem 3]. For a disjoint union take the maximum over components, since circular colourability is monotone in the ratio [21]. Test the O(N2)O(N^2) pairs with 1≤q≤p/21 \le q \le p/2 and p≤Np \le N and return the least feasible ratio by integer comparison. We use the usual chromatic conventions 1 for a nonempty edgeless graph and 0 for the empty graph.

The theorem includes homomorphism to an input odd cycle. For recognition, reject bipartite graphs and apply the threshold test at p=hp=h, q=(h−1)/2q=(h-1)/2, where hh is the odd girth.

Corollary 16. Computing χc(G)\chi_c(G) and deciding both problems of Theorem 1 are fixed-parameter tractable for feedback vertex number plus maximum degree.

Proof. Deleting all edges incident with a minimum feedback vertex set leaves a forest. Thus r≤Δ(G)fvs⁡(G)r \le\Delta(G)\operatorname{fvs}(G), and Theorem 15 needs only the graph as input.

Corollary 17. On graphs of order NN and finite girth gg, computing χc(G)\chi_c(G) and solving both problems of Theorem 1 take 2O((N/g)2)∣I∣O(1)2^{O((N/g)^2)}|I|^{O(1)} time. The running time is polynomial whenever g=Ω(Nlog⁡log⁡N/log⁡N)g=\Omega(N\log\log N/\log N).

Proof. Write D=N/qD=N/q. We first bound rr for every DD. Discard tree components, which contribute zero to rr. Put s=⌊(g−3)/8⌋s=\lfloor(g-3)/8\rfloor. In each remaining component take a maximal set of centres pairwise at distance greater than 2s2s. The radius-ss balls about all centres are disjoint. Each contains at least s+1s+1 vertices, since the component is connected and has at least gg vertices. Thus the total number of centres is at most N/(s+1)=O(N/g)N/(s+1)=O(N/g).

Maximality puts every vertex within distance 2s2s of a centre. Simultaneous breadth-first search from the centres partitions the graph into rooted trees of radius at most 2s2s. Contract the tree edges. An extra edge internal to a tree would close a cycle of length at most 4s+14s+1. Two edges joining the same pair of trees would, with the paths in the two trees, form a cycle of length at most 8s+28s+2. Both lengths are less than gg. Hence the contraction gives a simple graph on O(N/g)O(N/g) vertices. Each tree-edge contraction preserves rr, so r=O(D2)r=O(D^2). Theorem 15 gives the first time bound.

To obtain the polynomial range, suppose D=O(log⁡N/log⁡log⁡N)D=O(\log N/\log\log N). Then r=O(D2)=O(log⁡2N)r=O(D^2)=O(\log^2 N). Connect the original components by bridges, giving a simple graph of the same girth with N+r−1N+r-1 edges. For r≥3r\ge3, the girth bound of Bollobás and Szemerédi [10] gives g=O((N+r)log⁡r/r)g=O((N+r)\log r/r). Since N+r=O(N)N+r=O(N), we obtain r=O(Dlog⁡r)=O(log⁡N)r=O(D\log r)=O(\log N). Theorem 15 now takes polynomial time, as it also does for r<3r<3.

The girth bound counts all cycles. For core recognition a companion algorithm [16] gives polynomial time already at odd girth Ω(N/log⁡N)\Omega(N/\log N), by using the odd girth as the target length. For an independently supplied target, its length can be much smaller than the source girth. The case of girth Ω(N/log⁡N)\Omega(N/\log N) and unrestricted odd target length remains open in these bounds.

Encoding and checking decompositions

Emitting the graph. Let NN denote the length of the explicitly encoded input, including any supplied decomposition. Give output vertices identifiers consisting of a type tag and a constant number of indices: an original vertex, a residue, a reference position, or an original edge and a link position. All indices are polynomially bounded in NN, so an identifier occupies O(log⁡N)O(\log N) bits. Nested counters enumerate the vertices and edges. List membership and original adjacency are decided by rescanning the input; original edges are emitted once, in increasing endpoint order. If consecutive integer identifiers are required, the rank of a tuple can be recomputed by enumerating its predecessors. Output nn in binary; the corresponding cycle can also be enumerated explicitly. Neither an adjacency table nor a list of output vertices is stored.

Emitting a tree decomposition. Fix an order on the input bags. A reference gadget belongs to the first bag containing vv; an original-edge link belongs to the first bag containing both endpoints. Such an owning bag exists by vertex or edge coverage and can be found by scans.

The reference-path root has coordinate r=max⁡{2,d}r=\max\{2,d\}. Its bag has parent the owning input bag; the bag at any other private coordinate jj has parent j+1j+1 if j<rj<r, and j−1j-1 if j>rj>r, within the same copy. Its vertex parent follows the same rule, except that the root’s vertex parent is hvh_v. Emit the input bags with A,BA,B added, and the reference bags {A,B,x,parent⁡(x)}\{A,B,x,\operatorname{parent}(x)\}. These formulas require only coordinate comparisons and give the decomposition of JJ directly.

A required direct domain edge belongs to its copy’s root bag when d≥2d\ge2, and to its owning input bag when d=0d=0 or d=1d=1. An original edge belongs to its owning input bag. Emit each subdivision chain of size-three bags from § 3.1 at that bag. Parents within a chain are consecutive indices, so both bags and decomposition edges can be emitted without a general forest traversal.

Emitting a path decomposition. Implement the two stages of § 3.2 in order. For each input bag, emit its enlargement by A,BA,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 JJ. 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 JJ. 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 bb bags, either construction uses O(b+mn2+(e+f)n)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)O(\log N) workspace, polynomial time, and polynomial output length, independently of the input width.

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 bb steps, where bb is the number of bags. This checks that the index graph is a tree using counters and rescans.

For each graph vertex vv, count its occurrence bags, say ava_v, and the tree edges with both endpoints among those bags, say eve_v. The induced index subgraph is a forest, so it is nonempty and connected exactly when av>0a_v > 0 and ev=av−1e_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.

Lean verification

The artifact uses Lean 4.35.0 [11] and mathlib v4.35.0 [17]. 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 848545a, run python3 scripts/check_formalization.py from the repository root [9]. It builds the library, checks for proof admissions and audits the principal declarations. 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.

References

  1. [1]K. A. Abrahamson, R. G. Downey and M. R. Fellows. Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues. Annals of Pure and Applied Logic 73(3):235–276, 1995. doi:10.1016/0168-0072(94)00034-Z.DOI
  2. [2]Antoine Amarilli. Complexity of the homomorphism problem parameterized by treewidth. Theoretical Computer Science Stack Exchange, question 34877, June 2, 2016, with a comment on workshop reductions, May 30, 2025. https://cstheory.stackexchange.com/q/34877.
  3. [3]Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk and Michał Pilipczuk. On the complexity of problems on tree-structured graphs. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022), LIPIcs, vol. 249, pp. 6:1–6:17. Schloss Dagstuhl, 2022. doi:10.4230/LIPIcs.IPEC.2022.6.DOI
  4. [4]Hans L. Bodlaender, Carla Groenland, Jesper Nederlof and Céline Swennenhuis. Parameterized problems complete for nondeterministic FPT time and logarithmic space. Information and Computation 300:105195, 2024. doi:10.1016/j.ic.2024.105195.DOI
  5. [5]Hans L. Bodlaender, Carla Groenland and Michał Pilipczuk. Parameterized complexity of Binary CSP: vertex cover, treedepth, and related parameters. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), LIPIcs, vol. 261, pp. 27:1–27:20. Schloss Dagstuhl, 2023. doi:10.4230/LIPIcs.ICALP.2023.27.arxiv.org/abs/2208.12543
  6. [6]Hans L. Bodlaender, Carla Groenland and Michał Pilipczuk. Parameterized complexity of Binary CSP: vertex cover, treedepth, and related parameters. Full version, arXiv:2208.12543v5, 2023.arxiv.org/abs/2208.12543
  7. [7]Clément Carbonnel. Faster algorithms for graph homomorphism via tractable constraint satisfaction. arXiv:2602.23000v2, 2026.arxiv.org/abs/2602.23000
  8. [8]Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Loksh­tanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.DOI
  9. [9]Jason Davies. Odd-cycle homomorphism: Lean formalisation and executable checks. Software repository, 2026. Version 848545a. https://github.com/jasondavies/odd-cycle-homomorphism.
  10. [10]Béla Bollobás and Endre Szemerédi. Girth of sparse graphs. Journal of Graph Theory 39(3):194–200, 2002. doi:10.1002/jgt.10023.DOI
  11. [11]Leonardo de Moura and Sebastian Ullrich. The Lean 4 theorem prover and programming language. In Automated Deduction – CADE 28, LNCS, vol. 12699, pp. 625–635. Springer, 2021. doi:10.1007/978-3-030-79876-5_37.DOI
  12. [12]Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. Springer, 2006. doi:10.1007/3-540-29953-X.DOI
  13. [13]A. M. H. Gerards. Homomorphisms of graphs into odd cycles. Journal of Graph Theory 12(1):73–83, 1988. doi:10.1002/jgt.3190120108.DOI
  14. [14]Hossein Hajiabolhassan and Ali Taherkhani. On the circular chromatic number of graph powers. Journal of Graph Theory 75(1):48–58, 2014. doi:10.1002/jgt.21722.DOI
  15. [15]A. Kostochka, J. Nešetřil and P. Smolíková. Colorings and homomorphisms of degenerate and bounded degree graphs. Discrete Mathematics 233:257–276, 2001. doi:10.1016/S0012-365X(00)00245-4.DOI
  16. [16]Jason Davies. Homomorphisms to long odd cycles in time exponential in the order-to-length ratio. Companion manuscript, 2026. Distributed alongside this paper as long-odd-cycles.pdf.
  17. [17]The mathlib Community. The Lean mathematical library. In Certified Programs and Proofs (CPP 2020), pp. 367–381. ACM, 2020. doi:10.1145/3372885.3373824.DOI
  18. [18]Karolina Okrasa and Paweł Rzążewski. Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs. SIAM Journal on Computing 50(2):487–508, 2021. doi:10.1137/20M1320146. Preprint version: arXiv:1906.08371v3, 2020.DOI
  19. [19]Marta Piecyk and Paweł Rzążewski. Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), LIPIcs, vol. 187, pp. 56:1–56:17. Schloss Dagstuhl, 2021. doi:10.4230/LIPIcs.STACS.2021.56.
  20. [20]Andrew Vince. Star chromatic number. Journal of Graph Theory 12(4):551–559, 1988. doi:10.1002/jgt.3190120411.DOI
  21. [21]Xuding Zhu. Circular chromatic number: a survey. Discrete Mathematics 229(1–3):371–410, 2001. doi:10.1016/S0012-365X(00)00217-X.DOI

Paper details

vlnc:W_k7pecfs9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Anthropic Claude Code Claude Opus 5.5, OpenAI Codex GPT-6-Astra

View statement
Looking for related papers…
Contents