On the balanced case of the Brualdi-Shen conjecture on 4-cycle decompositions of Eulerian bipartite tournaments - Rafael Del Valle Vega (GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB, 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=(UV, 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.