Conservative weightings and ear-decompositions of graphs

DOI10.1007/BF01202790zbMath0779.05033MaRDI QIDQ2367443

András Frank

Publication date: 16 August 1993

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

matching; ear-decomposition; weighting; critical graph

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

94B60: Other types of codes

05C75: Structural characterization of families of graphs

Related Items

On generalizations of matching-covered graphs, Complexity of finding a join of maximum weight, Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs, The covering radius of the cycle code of a graph, Maximality of the cycle code of a graph, A generalization of Petersen's theorem, Complexity of circuit intersection in graphs, On a matroid defined by ear-decompositions of graphs, Approximating max-min weighted \(T\)-joins, The edge-orientation problem and some of its variants on weighted graphs, Disclosing Barriers: A Generalization of the Canonical Partition Based on Lovász’s Formulation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A quick proof of Seymour's theorem on t-joins
• Undirected distances and the postman-structure of graphs
• Covering directed and odd cuts
• On Odd Cuts and Plane Multicommodity Flows
• 2-Matchings and 2-covers of hypergraphs
• A Minimax Theorem for Directed Graphs
• Matching, Euler tours and the Chinese postman
• Paths, Trees, and Flowers