TOWARDS A DICHOTOMY FOR THE LIST SWITCH HOMOMORPHISM PROBLEM FOR SIGNED GRAPHS

NEW

Problem: Reconstructed conjecture: for every finite purple-red signed graph $H$, the following are equivalent:

1. the bipartite resolution $\mathcal B_H=K_2^{\mathrm{purple}}\times H$ has no invertible pairs and no chains;
2. $\mathcal B_H$ has a parity-symmetric special bipartite-min ordering;
3. the switching graph $\mathcal S_H$ has a semi-conservative WNU polymorphism.

Result: The conjecture is false.

Let $H$ be the two-vertex pr-graph with vertices $x,y$, one pure red edge $xy$, no loops, and no purple edges.

Then $\mathcal B_H$ has partite sets

and exactly the two pure red edges

So its underlying graph is a matching of size $2$.

• There are no chains, because there are no purple edges.
• There are no bipartite invertible pairs: the pair digraph has two directed 2-cycles

so no ordered pair reaches its reverse.

Thus condition (i) holds.

But $\mathcal B_H$ has no parity-symmetric bipartite-min ordering. Indeed, parity symmetry forces

If $x_0<y_0$, then $x_1<y_1$, and the bipartite-min underbar property applied to the two edges $x_0y_1$ and $y_0x_1$ would force an edge $x_0x_1$, i.e. a loop at $x$ in $H$, impossible. The case $y_0<x_0$ similarly forces the nonexistent edge $y_0y_1$. Hence condition (ii*) fails.

For completeness, condition (iii) actually holds: identify $V(\mathcal S_H)$ with $\{0,1\}^2$, where red edges flip the first coordinate and preserve the second, while blue edges flip both. The coordinatewise majority operation preserves both edge relations and all switch-closed lists, so it is a semi-conservative near-unanimity polymorphism.

Therefore (i) and (iii) hold but (ii*) fails.

The defect is the parity-symmetry requirement; dropping it recovers the weaker original formulation, while restricting to reflexive pr-graphs gives a known true theorem.

Citation: Counterexample above is elementary. Related proven reflexive case: Kim–Siggers, “Towards a dichotomy for the switch list homomorphism problem for signed graphs,” Kyungpook Math. J. 63 (2023), 355–372, Theorem 4.3; using Bok–Brewster–Hell–Jedličková–Rafiey, arXiv:2206.01068.