Conservative weightings and ear-decompositions of graphs

DOI10.1007/BF01202790zbMath0779.05033OpenAlexW1576926907MaRDI QIDQ2367443

András Frank

Publication date: 16 August 1993

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01202790

zbMATH Keywords

matchingear-decompositionweightingcritical graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Other types of codes (94B60) Structural characterization of families of graphs (05C75)

Related Items (21)

Eulerian ideals ⋮ Complexity of circuit intersection in graphs ⋮ On a matroid defined by ear-decompositions of graphs ⋮ On combinatorial properties of binary spaces ⋮ Two-Connected Spanning Subgraphs with at Most $\frac{10}{7}{OPT}$ Edges ⋮ Joins, ears and Castelnuovo-Mumford regularity ⋮ Approximation algorithms for flexible graph connectivity ⋮ Beating the Integrality Ratio for $s$-$t$-Tours in Graphs ⋮ Decreasing behavior of the depth functions of edge ideals ⋮ Approximating max-min weighted \(T\)-joins ⋮ 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 ⋮ On generalizations of matching-covered graphs ⋮ Complexity of finding a join of maximum weight ⋮ The edge-orientation problem and some of its variants on weighted graphs ⋮ A generalization of Petersen's theorem ⋮ Associated primes of powers of edge ideals and ear decompositions of graphs ⋮ Graft analogue of general Kotzig-Lovász decomposition ⋮ Degree and regularity of Eulerian ideals of hypergraphs ⋮ Disclosing Barriers: A Generalization of the Canonical Partition Based on Lovász’s Formulation ⋮ Maximality of the cycle code of a graph

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

This page was built for publication: Conservative weightings and ear-decompositions of graphs