Balanced cycles and holes in bipartite graphs (Q1297428): Difference between revisions

The authors show that the following two problems are equivalent for a bipartite graph \(G\) where each edge has been assigned a weight \(+1\) or \(-1\): (1) Determine whether \(G\) contains a cycle whose weight is divisible by 4. (2) Determine whether \(G\) contains a chordless cycle whose weight is divisible by 4. They describe a linear algorithm to decide whether a given signed (edges weighted \(+1\) or \(-1\)) bipartite graph contains a chordless cycle whose weight is divisible by 4. Finally it is shown how to decide whether it is possible to assign weights \(+1\), \(-1\) to each edge of a bipartite graph so that the above properties hold.