On the balanced case of the Brualdi-Shen conjecture on 4-cycle decompositions of Eulerian bipartite tournaments - Rafael Del Valle Vega (Electronic Journal of Graph Theory and Applications (EJGTA), 2015)
The Brualdi-Shen Conjecture on Eulerian Bipartite Tournaments states that any such graph can be decomposed into oriented 4-cycles. In this article we prove the balanced case of the mentioned conjecture. We show that for any $2n× 2n$ bipartite graph $G=(U\cup V, E)$ in which each vertex has $n$-neighbors with biadjacency matrix $M$ (or its transpose) there is a proper edge coloring of a column permutation of $M$ denoted $M^{σ}$ in which the nonzero entries of each of the $first$ $n$ columns are colored with elements from the set $\{n+1, n+2, …, 2n\}$ and the nonzero entries of each of the $last$ $n$ columns are colored with elements from the set $\{1, 2, …, n\}$ and if the nonzero entry $M^{σ}_{r,j}$ is colored with color $i$ then $M^{σ}_{r,i}$ must be a zero entry. Such a coloring will induce an oriented 4-cycle decomposition of the bipartite tournament corresponding to $M$. We achieve this by constructing an euler tour on the bipartite tournament which avoids traversing both pair of edges of any two internally disjoint $s$-$t$ 2-paths consecutively, where $s$ and $t$ belong to $V$.