Kempe Reachability with $k\geq 3$ Colors Is $\mathsf{PSPACE}$-Complete on Claw-Free Graphs

1 Introduction

• PSPACE-completeness holds for every fixed k ≥3 on line graphs of connected simple k-regular graphs, and hence on connected (2k −2)-regular claw-free graphs.The equivalent edge-coloring problem is PSPACE-complete on connected simple k-regular graphs.Source: §1 · p. 3
• For k ≥4, instances with maximum degree at most k are yes-instances, while the paper's hard claw-free instances attain the maximum possible degree 2k −2.The intermediate bounds k + 1 through 2k −3 remain unsettled; with four colors, degree five is specifically left open.Source: §1 · pp. 2–3
• The reduction starts from restricted cubic NCL reachability and preserves whether the two source orientations are connected through legal edge reversals.The source is a connected simple cubic AND/OR constraint graph; each legal configuration has incoming weight at least two at every vertex.Source: §1 · p. 3
• A fixed Tait coloring labels the prepared source edges consistently, while a protected-pair replacement restricts each OR vertex to five local direction patterns.The replacement preserves reachability between corresponding configurations and introduces no loops.Source: §1 · pp. 3–4
• Gates encode source vertices and wires encode directions; paired wire-end colors represent inward or outward positions, and negators make both ends record one direction.Triangles coordinate the three incident wires so every proper network coloring can be read as a legal source configuration.Source: §1 · p. 4
• Triangle locks ensure a Kempe change alters at most one incident source direction, so arbitrary coloring sequences cannot connect source configurations lacking a legal reversal path.When several directions change, their source edges have no common endpoint and can be reversed one at a time through legal configurations.Source: §1 · p. 4
• For k = 3, each legal source reversal is realized by one Kempe change; for k > 3, the extra colors stay fixed while sequences simulate the reversals.The fixed labels from τ align choices along wires.Source: §1 · pp. 4, 6
• The construction completes the network into a connected simple k-regular graph, then takes its line graph to obtain a connected claw-free graph of degree 2k −2.The line-graph conversion makes edge-Kempe changes correspond exactly to vertex-Kempe changes.Source: §1 · p. 6

2.1 Graphs, Colorings, and Kempe Changes

• Edge-Kempe changes correspond exactly to Kempe changes on line graphs, which are claw-free and preserve connectedness and regularity as degree 2k −2.In particular, a connected k-regular graph with an edge has a connected (2k −2)-regular line graph.Source: §2.1 · p. 8

2.2 Multipoles

• Multipoles encode edge-colorings through dangling edges and Kempe moves along alternating paths or cycles; each color’s dangling-edge count has the parity of the internal-vertex count.Connectors group ordered pairs of dangling edges and record their ordered color states and equality type.Source: §2.2 · pp. 8–9

2.3 Protected Constraint Logic

• A protected replacement preserves and reflects configuration reachability while producing loopless replacements with protected OR pairs in every legal configuration.Each replaced OR vertex uses a 13-vertex gadget; the endpoint completions can be chosen independently.Source: §2.3 · p. 12

2.4 The Source Used by the Reduction

• A linear-time preprocessing preserves reachability and yields a Tait-colored protected source; the resulting configuration-to-configuration problem is PSPACE-complete.For a source X0, the output has at most 10|V(X0)| vertices; after protection and Tait preprocessing the size is at most 130n0, where n0 is the order of the original simple source.Source: §2.4 · p. 13

2.5 Constructing a Tait-Colored Source

• The construction assigns distinct local colors at each old vertex, replaces mismatched edges with three-edge paths through new OR vertices, and attaches paired ports to copies of Q.The constrained edge terminator forces its attaching edges inward, so each new OR vertex receives inflow from the path.Source: §2.5 · pp. 13–15
• Every orientation of Q meeting the four AND vertices’ inflow constraints directs both ports toward Q.This forces each attached OR vertex’s port toward its core in every legal configuration.Source: §2.5 · p. 14
• Each color has an even number of new ports, allowing them to be paired, and the resulting edge coloring gives every vertex of X three distinct incident colors.The parity follows by counting incidences of each color at vertices of X0; each mismatched edge contributes one port for each of its endpoint colors.Source: §2.5 · pp. 15–16
• The maps up and down take legal configurations between X0 and X, with down preserving legality and protected pairs.For each old vertex, down’s inflow is at least the corresponding inflow in X; transformed incoming incidences remain incoming, preserving protection.Source: §2.5 · pp. 15–17
• The resulting graph X is connected and loopless, has at most 10|V(X0)| vertices, and can be constructed in linear time.The bound follows from adding 2r path vertices and 4r core vertices for r mismatched edges.Source: §2.5 · p. 16
• The maps up and down preserve reachability in both directions, so X0 configurations are connected by legal reversals exactly when their images in X are.A reversal of a mismatched old edge lifts to at most three legal reversals in X, while a reversal in X projects to no more than one in X0.Source: §2.5 · p. 17

3.1 The Negator

• For every coloring, the negator has exactly one equal connector, and its residual edges use precisely the colors absent from the unequal connector; it has 8k −17 internal vertices and k + 2 dangling edges.Source: §3.1 · p. 19

3.3 The Network

• Each source edge receives its own wire of negators, with alternating connector equality types and a length that compensates for the endpoint slot polarities.The network includes one gate and one triangle per source vertex, and distinct wires for parallel source edges.Source: §3.3 · p. 21

3.4 The Triangle and the Gates

• At each source vertex, the triangle edges have distinct colors, and an unequal slot’s connector colors equal the pair of colors on its two incident triangle edges.The triangle residual edges carry the complementary colors, distinguishing the three slot pairs.Source: §3.4 · pp. 22–23

3.2 The Gates

• The OR gate requires some slot to represent 1, while in the AND gate, slot 0 representing 0 forces slots 1 and 2 to represent 1.The OR gate uses three negators; the AND gate uses two negators and three new vertices.Source: §3.2 · p. 20, §3.4 · p. 23

3.5 The Legal Configuration of a Coloring

• Each wire’s endpoint slots read opposite bits, so directing the source edge toward the endpoint reading 1 yields an orientation satisfying the gate laws and therefore a legal configuration.Source: §3.5 · p. 23
• Each coloring projects to a legal orientation of X: the two endpoint slots for every edge represent complementary bits, and each vertex’s represented state is legal.The wire’s connector equality types alternate, with the wire length chosen so the endpoint bits sum to an odd number; the resulting orientation also satisfies the global protection promise at OR vertices.Source: §3.5 · p. 24

3.6 One Kempe Change

• A Kempe exchange changes the projected orientation only on a matching of edges, whose directions can be reversed in any order through legal configurations.At each vertex, at most one gate slot changes its represented bit; consequently, the projections of any two Kempe-reachable colorings are connected by legal edge reversals.Source: §3.6 · pp. 24–25

4.1 Three Colors and the Negator

• For opposite-equality connector states, W3 has a unique coloring, and its color-pair Kempe routes connect specified dangling edges; an automorphism exchanges connectors while fixing the residual edge.The routes determine which dangling edges each Kempe chain joins, including paths through the residual edge.Source: §4.1 · pp. 27, 29

4.2 Canonical Colorings

• Canonical gate colorings extend each legal source state properly, and assembling them along wires and triangles yields a proper coloring Cx whose projection is x.For the AND gate, the negator residual colors are e(g0) = 2 − 2β1 and e(g1) = 1 + β0.Source: §4.2 · p. 30

4.3 The Nine Local Transitions

• Seven boundary traces cover all nine local transitions: each yields a Kempe path changing only the active slot and exactly the target canonical gate coloring.Each path starts at the changing slot’s second edge, ends at a residual dangling edge, and avoids all other slot edges.Source: §4 · p. 25, §4.3 · p. 31, Table 2 · p. 31
• The nine local gate transitions are realized by Kempe exchanges that change the prescribed slot and boundary colors while leaving other slot coordinates fixed.Uniqueness of the coloring inside each negator then gives the canonical target coloring.Source: §4.3 · pp. 31–32

4.4 One Global Kempe Path

• Each legal source reversal is simulated by one Kempe change: local gate paths join through the reversed wire into a whole bichromatic path.The path leaves inactive slots unchanged, so inactive wires retain their canonical coloring.Source: §4.4 · p. 32

4.5 From Three Colors to k Colors

• For k ≥ 4, fixed added edges carry colors 3 through k − 1; deleting them leaves F^3_X with 3(k − 3) digons on each first output edge and k − 3 on each second.The added-edge selection is made so the remaining network has the cubic form with digons inserted into edges.Source: §4.5 · p. 33

4.6 Lifting the Moves

• Inserting digons preserves Kempe moves: chains lift through digons, while extra chains consist of a digon's parallel edges; repairing their color order lifts each move sequence.A coloring extends uniquely by assigning the parallel edges the two colors missing from the replaced edge in a fixed order.Source: §4.6 · p. 35
• For every k ≥ 3, each legal source configuration has a coloring of F^k_X projecting to it, and reachability of configurations implies Kempe reachability of their colorings.The k-color simulation lifts the three-color moves while keeping added-edge colors fixed.Source: §4.6 · p. 36

5 Proof of Theorem 1.1

• If both edges of a color pair at each internal vertex belong to a chosen edge set, that set is a union of Kempe chains and can be exchanged one chain at a time.Source: §5 · p. 36

5.1 Two Copies

• Joining two copies along their dangling edges gives a k-regular multigraph, and reachability is preserved even for colorings that are not identical on both copies.Reading a coloring through either copy makes each move project to exchanges on a union of Kempe chains in the original multipole.Source: §5.1 · pp. 37–38

5.2 Removing Parallel Edges

• Replacing each vertex by Kk,k−1 produces a connected simple k-regular graph and preserves edge-Kempe reachability between the prescribed extensions.Every coloring projects to a proper coloring of the multigraph, with each move projecting to one edge-Kempe change or changing no projected edge; prescribed sequences also extend.Source: §5.2 · pp. 38–39

5.3 The Main Result

• Legal configurations are reachable exactly when their constructed edge-colorings are edge-Kempe reachable; the reduction has linear size for fixed k and yields connected claw-free line graphs.The proof projects target sequences back to legal reversals and lifts the simulation forward.Source: §5.3 · p. 41
• For every k ≥3, each nonempty connected simple cubic AND/OR constraint graph has a polynomial-time reachability-preserving map to edge-colorings of a connected simple k-regular graph.The construction composes protected replacement and Tait preprocessing with the target map; the cited corollary also gives a graph-order bound, whose formula is not present in the supplied passages.Source: §5.3 · p. 42
• The line graph of each constructed graph is connected, claw-free, and (2k −2)-regular, with the same reachability equivalence when edge-colorings are read as vertex colorings.The correspondence follows because line-graph Kempe changes preserve the edge-Kempe move relation.Source: §5.3 · p. 42
• For every fixed k ≥3, Kempe Reachability is PSPACE-complete on line graphs of connected simple k-regular graphs and on connected (2k −2)-regular claw-free graphs.The proof combines polynomial-space membership with reductions that preserve reachability and Kempe moves.Source: §5.3 · p. 42

5.4 Concluding Remarks

• For fixed k ≥4, the hard instances attain degree 2k −2, leaving unresolved claw-free restrictions with maximum degree k + 1 through 2k −3, including four colors and degree five.Every instance with maximum degree at most k is a yes-instance; the construction's global source protection limits the local transitions its gates simulate.Source: §5.4 · pp. 42–43
• A polynomial-time complete invariant for Tait-coloring Kempe classes would imply P = PSPACE, while known Gröbner-basis methods characterize equivalence but are noted as infeasible for large graphs.The remarks also distinguish necessary-condition invariants and cubic bipartite questions, and cite results on planar cubic graphs, planar bipartite graphs, projective-plane embeddings, and bipartite examples with 2n classes [9].Source: §5.4 · p. 43

• ChatGPT 6 Pro and Claude Fable 5.1 assisted with developing and reviewing mathematical arguments and drafting and revising the paper.Source: AI Declaration · p. 43
• The author takes full responsibility for the paper’s correctness and content.Source: AI Declaration · p. 43