Balanced cycles and holes in bipartite graphs
type: Item
instance of: scholarly article
title: Balanced cycles and holes in bipartite graphs
zbMATH Open document ID: 0939.05050
DOI: 10.1016/S0012-365X(98)00283-0
author: Michele Conforti
author: Kristina Vušković
author: Gérard Cornuéjols
published in: Discrete Mathematics
publication date: 2000-07-05T00:00:00Z
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.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C22
zbMATH DE Number: 1321789
zbMATH Keywords: signed graph
zbMATH Keywords: bipartite graph
zbMATH Keywords: chordless cycle
zbMATH Keywords: linear algorithm
reviewed by: Jørgen Bang-Jensen
MaRDI profile type: Publication
cites work: A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
cites work: Q3924253
cites work: Dividing a Graph into Triconnected Components
cites work: Alpha-balanced graphs and matrices and GF(3)-representability of matroids
cites work: Q4004142
cites work: Forbidden subgraphs and graph decomposition
cites work: On a Class of Totally Unimodular Matrices
Wikidata QID: Q126472657
description: scientific article; zbMATH DE number 1321789