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

NEW

Problem: Reconstructed Conjecture 1.4: for every finite purple-red graph $H$ (undirected, loops allowed, no pure-blue edges), its bipartite resolution

has a special bipartite-min ordering iff it has one invariant under the parity flip $(i,v)\mapsto(1-i,v)$. A parity-symmetric ordering means the two partite orders induce the same order on $V(H)$. This is exactly the formulation supported by the quoted paper and its definitions of $\mathcal B_H$, special ordering, and parity symmetry.

Result: The conjecture is false.

Let $H$ have vertices $p,r,c$, no loops, one purple edge $cp$, and one pure red edge $cr$. This is a connected $\mathrm{pr}$-graph.

In $\mathcal B_H$, write the two parts as

Use the orders

With rows $0p,0r,0c$ and columns $1c,1p,1r$, the underlying adjacency matrix is

This matrix satisfies the bipartite-min underbar condition: whenever $i\le j$, $k\le \ell$, and entries $(i,\ell)$, $(j,k)$ are $1$, entry $(i,k)$ is also $1$.

The ordering is special: the only vertex with both a purple and a pure red neighbour is $c$, and in both partite orders the purple neighbour $p$ precedes the red neighbour $r$.

Now suppose a parity-symmetric bipartite-min ordering existed. Then both parts induce one common order $<$ on $\{p,r,c\}$. For the edge $cp$, let $x<y$ be the two endpoints in this common order. In $\mathcal B_H$, edges $0x\,1y$ and $0y\,1x$ exist. The underbar property would force $0x\,1x$, i.e. a loop at $x$ in $H$, contradiction. Thus no parity-symmetric bipartite-min ordering exists.

So $\mathcal B_H$ has a special bipartite-min ordering but no parity-symmetric one.

Diagnosis: the failure is caused by the missing reflexivity/loop hypothesis, not by disconnectedness or absence of colours. The example is connected and has both a purple and a pure red edge. A natural repair is to restrict to reflexive $\mathrm{pr}$-graphs; that repaired version is known true.

Audit: the example is a finite $\mathrm{pr}$-graph, the displayed ordering satisfies exactly the special bipartite-min requirements, and the contradiction rules out every parity-symmetric ordering.

Citation: No prior citation is needed for the counterexample. The reflexive repaired statement is proved in Hyobin Kim and Mark Siggers, “Towards a dichotomy for the list switch homomorphism problem for signed graphs,” Kyungpook Math. J. 63 (2023), 355–372, Theorem 4.4.