Ear-decompositions of matching-covered graphs

DOI10.1007/BF02579346zbMath0516.05047MaRDI QIDQ1052341

László Lovász

Publication date: 1983

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

matchingear-decompositioncyclomatic numbersKoenig propertymatching- covered subgraphsmatching-covered

Mathematics Subject Classification ID

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

Related Items

\(k\)-cycle resonant graphs, On some conjectures concerning critical independent sets of a graph, On Two Unsolved Problems Concerning Matching Covered Graphs, Critical independent sets of König-Egerváry graphs, Computing unique maximum matchings in \(O(m)\) time for König-Egerváry graphs and unicyclic graphs, Matching extension and the genus of a graph, WELL-COVERED GRAPHS: A SURVEY, Some more updates on an annihilation number conjecture: pros and cons, On approximability of optimization problems related to red/blue-split graphs, Two more characterizations of König-Egerváry graphs, Removable ears of 1-extendable graphs, Critical and maximum independent sets of a graph, The maximum number of maximum dissociation sets in trees, Matching covered graphs with three removable classes, Even cycles and perfect matchings in claw-free plane graphs, Ear decomposition and induced even cycles, A characterization of minimal non-Seymour graphs, Removable edges in Halin graphs, On critical difference, independence number and matching number of graphs, Automated conjecturing. I: Fajtlowicz's Dalmatian heuristic revisited, Planar \(k\)-cycle resonant graphs with \(k=1,2\), Reducible chains of planar 1-cycle resonant graphs, Forbidden subgraphs and the König-Egerváry property, On maximum matchings in König-Egerváry graphs, The complexity of König subgraph problems and above-guarantee vertex cover, Some variants of perfect graphs related to the matching number, the vertex cover and the weakly connected domination number, A characterization of Konig-Egervary graphs using a common property of all maximum matchings, Combinatorial and spectral properties of König-Egerváry graphs, Minimal bricks, On essentially 4-edge-connected cubic bricks, K ₄ -free and C6¯-free Planar Matching Covered Graphs, New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition, Faces of Birkhoff Polytopes, König-Egerváry graphs, 2-bicritical graphs and fractional matchings, Forbidden subgraphs and the Kőnig property, On \((g,f)\)-uniform graphs, Reduced 2-to-1 maps and decompositions of graphs with no 2-to-1 cut sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A characterization of the graphs in which the transversal number equals the matching number
• On n-extendable graphs
• Matchings in regular graphs
• On minimal elementary bipartite graphs
• Regularisable graphs I
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• Rank of maximum matchings in a graph
• A theorem on connected graphs in which every edge belongs to a 1-factor
• A Theorem on k-Saturated Graphs
• Paths, Trees, and Flowers
• A Simplified Form for Nearly Reducible and Nearly Decomposable Matrices
• On the structure of factorizable graphs
• The 1-Factors of Oriented Graphs