Edge Coloring of Products of Signed Graphs

NEW

Problem: Let $S=(G,\sigma)$ be any finite simple signed graph whose underlying graph $G$ is obtained from two disjoint copies of $K_n$ by adding one edge joining one vertex of the first clique to one vertex of the second. Thus $\Delta(G)=n$. In Behr’s signed edge-coloring sense, prove that

Result: The conjecture is true.

Let the two bridge vertices be $a_0,b_0$. It is enough to construct an $n$-edge-coloring, since any signed edge-coloring needs at least $\Delta(S)=n$ colors at a vertex of degree $n$.

We use the following elementary fact: any signed path can be colored with a prescribed pair of colors $\{\pm i\}$. Starting at one end, choose one incidence color $i$; then the edge sign determines the color at the other endpoint, and at each internal vertex choose the opposite member of $\{\pm i\}$ for the next edge. Thus adjacent incidences differ. A matching can always be colored with color $0$, when $0$ is available.

If $n=2m$ is even, use Walecki’s decomposition of $K_{2m}$ into $m$ Hamiltonian paths, chosen so that the distinguished vertex is an endpoint of the first path. Apply this decomposition separately to both cliques, with $a_0,b_0$ endpoints of the first paths. Join those two first paths by the bridge; this gives one longer path. The remaining corresponding path pairs form disjoint unions of paths. Hence the whole underlying graph decomposes into $m$ linear forests. Color the $j$-th forest with the pair $\{\pm j\}$, $j=1,\dots,m$. This gives a valid signed $2m=n$-edge-coloring.

If $n=2m+1$ is odd, use Walecki’s Hamiltonian-cycle decomposition of $K_{2m+1}$. Equivalently, for each clique and its distinguished vertex, one may decompose $K_{2m+1}$ into $m$ Hamiltonian paths plus a matching of size $m$ avoiding the distinguished vertex. Do this in both cliques. Color the two matchings together with the bridge by $0$; this is a matching because the clique matchings avoid $a_0,b_0$. The remaining edges are $m$ disjoint unions of paths, so color the $j$-th such forest with $\{\pm j\}$. This gives a valid signed $(2m+1)=n$-edge-coloring.

In both cases all edge-sign constraints are satisfied on each path by construction, and different forests use disjoint color sets. Therefore $\chi'(S)\le n$. Since $\chi'(S)\ge \Delta(S)=n$, we get

Citation: Uses the classical Walecki decomposition of complete graphs into Hamiltonian paths/cycles. The specific signed-graph conjecture is resolved here by the above decomposition argument.