A characterization of weakly bipartite graphs

DOI10.1006/JCTB.2001.2051MaRDI QIDQ1850558zbMATHOpenAlexFDO

Authors Bertrand Guenin

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

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

Recommendations

• scientific article; zbMATH DE number 1187139
• A short proof of Guenin's characterization of weakly bipartite graphs
• Signed analogs of bipartite graphs
• Ideal Binary Clutters, Connectivity, and a Conjecture of Seymour
• Homomorphism bounds of signed bipartite \(K_4\)-minor-free graphs and edge-colorings of \(2k\)-regular \(K_4\)-minor-free multigraphs

Cites work

• scientific article; zbMATH DE number 16723 (Why is no real title available?)
• scientific article; zbMATH DE number 16724 (Why is no real title available?)
• scientific article; zbMATH DE number 49899 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 508835 (Why is no real title available?)
• A Solution of the Shannon Switching Game
• A catalog of minimally nonideal matrices
• Combinatorial designs and related systems
• Combinatorial optimization. Packing and covering
• Compositions in the bipartite subgraph polytope
• Ideal 0, 1 matrices
• Lehman's forbidden minor characterization of ideal 0-1 matrices
• Matroids and multicommodity flows
• On the width—length inequality
• The Forbidden Minors of Binary Clutters
• The matroids with the max-flow min-cut property
• The max-cut problem on graphs not contractible to \(K_ 5\)
• Weakly bipartite graphs and the max-cut problem

Cited in

(27)

• Even-cycle decompositions of graphs with no odd-\(K_4\)-minor
• Idealness of \(k\)-wise intersecting families
• Single commodity-flow algorithms for lifts of graphic and cographic matroids
• Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs
• Max-Cut and containment relations in graphs
• scientific article; zbMATH DE number 4079483 (Why is no real title available?)
• On bipartite graphs with weak density of some subgraphs
• Packing odd circuits in Eulerian graphs
• Extended formulations in combinatorial optimization
• \textsc{max-cut} and containment relations in graphs
• Polyhedral results for the bipartite induced subgraph problem
• Idealness and 2-resistant sets
• Resistant sets in the unit hypercube
• scientific article; zbMATH DE number 1187139 (Why is no real title available?)
• Tight cycle relaxations for the cut polytope
• Min orderings and list homomorphism dichotomies for signed and unsigned graphs
• Lehman's theorem and the directed Steiner tree problem
• On fractional cut covers
• Paintshop, odd cycles and necklace splitting
• scientific article; zbMATH DE number 5054167 (Why is no real title available?)
• A short proof of Guenin's characterization of weakly bipartite graphs
• Solving VLSI design and DNA sequencing problems using bipartization of graphs
• Displaying blocking pairs in signed graphs
• Extended formulations in combinatorial optimization
• scientific article; zbMATH DE number 1093015 (Why is no real title available?)
• A survey on flows in graphs and matroids
• Idealness of \(k\)-wise intersecting families

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

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