A characterization of weakly bipartite graphs

DOI10.1006/jctb.2001.2051zbMath1030.05103OpenAlexW2094667324MaRDI QIDQ1850558

Guenin, Bertrand

Publication date: 10 December 2002

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/8b7c175d98d409c42e6b8417a78ef9ef0dfb7a32

zbMATH Keywords

minorsigned graphbinary cluttersideal clutters

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph minors (05C83) Signed and weighted graphs (05C22)

Related Items (22)

Idealness of k-wise Intersecting Families ⋮ A survey on flows in graphs and matroids ⋮ Lehman's Theorem and the Directed Steiner Tree Problem ⋮ Even-cycle decompositions of graphs with no odd-\(K_4\)-minor ⋮ Min orderings and list homomorphism dichotomies for signed and unsigned graphs ⋮ Packing odd circuits in Eulerian graphs ⋮ Solving VLSI design and DNA sequencing problems using bipartization of graphs ⋮ Polyhedral results for the bipartite induced subgraph problem ⋮ \textsc{max-cut} and containment relations in graphs ⋮ Displaying blocking pairs in signed graphs ⋮ Extended formulations in combinatorial optimization ⋮ Extended formulations in combinatorial optimization ⋮ max-cut and Containment Relations in Graphs ⋮ Idealness and 2-resistant sets ⋮ Single Commodity-Flow Algorithms for Lifts of Graphic and CoGraphic Matroids ⋮ On fractional cut covers ⋮ Paintshop, odd cycles and necklace splitting ⋮ Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs ⋮ Resistant Sets in the Unit Hypercube ⋮ A short proof of Guenin's characterization of weakly bipartite graphs ⋮ Tight Cycle Relaxations for the Cut Polytope ⋮ Idealness of \(k\)-wise intersecting families

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The max-cut problem on graphs not contractible to \(K_ 5\)
• Lehman's forbidden minor characterization of ideal 0-1 matrices
• Matroids and multicommodity flows
• Weakly bipartite graphs and the max-cut problem
• Compositions in the bipartite subgraph polytope
• The matroids with the max-flow min-cut property
• A catalog of minimally nonideal matrices
• Ideal 0, 1 matrices
• Combinatorial designs and related systems
• Combinatorial Optimization
• On the width—length inequality
• The Forbidden Minors of Binary Clutters
• A Solution of the Shannon Switching Game

This page was built for publication: A characterization of weakly bipartite graphs