Balanced cycles and holes in bipartite graphs

DOI10.1016/S0012-365X(98)00283-0MaRDI QIDQ1297428zbMATH OpenWikidataFDO

Authors Michele Conforti, Kristina Vušković, Gérard Cornuéjols

Publication date 5 July 2000

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(98)00283-0

zbMATH Keywords

bipartite graphchordless cyclelinear algorithmsigned graph

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Paths and cycles (05C38)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 597814
• Odd cycles and matrices with integrality properties
• A partition of bipartite graphs with 4-cycle and 8-cycle
• Independent cycles and paths in bipartite balanced graphs
• Perfect matchings of regular bipartite graphs

Cites work

• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• Alpha-balanced graphs and matrices and GF(3)-representability of matroids
• Dividing a Graph into Triconnected Components
• Forbidden subgraphs and graph decomposition
• scientific article; zbMATH DE number 3737730 (Why is no real title available?)
• scientific article; zbMATH DE number 53949 (Why is no real title available?)
• On a Class of Totally Unimodular Matrices

Cited in

(7)

• For which graphs does every edge belong to exactly two chordless cycles?
• Cycles in 2-factors of balanced bipartite graphs
• Balanced matrices
• Acyclically pushable bipartite permutation digraphs: an algorithm
• scientific article; zbMATH DE number 6501194 (Why is no real title available?)
• scientific article; zbMATH DE number 597814 (Why is no real title available?)
• Bisimplicial vertices in even-hole-free graphs

This page was built for publication: Balanced cycles and holes in bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1297428)