König-Egerváry graphs, 2-bicritical graphs and fractional matchings
From MaRDI portal
Publication:1825210
DOI10.1016/0166-218X(92)90273-DzbMath0684.05036OpenAlexW2082992040MaRDI QIDQ1825210
Jean-Marie Bourjolly, William R. Pulleyblank
Publication date: 1989
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(92)90273-d
Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (26)
New results relating independence and matchings ⋮ On the critical difference of almost bipartite graphs ⋮ A primal-dual approximation algorithm for \textsc{minsat} ⋮ Some more updates on an annihilation number conjecture: pros and cons ⋮ Graph factors and factorization: 1985--2003: a survey ⋮ On approximability of optimization problems related to red/blue-split graphs ⋮ A combinatorial column generation algorithm for the maximum stable set problem ⋮ When is \(G^2\) a König-Egerváry graph? ⋮ The price of defense ⋮ Critical independent sets and König-Egerváry graphs ⋮ A classification of 1-well-covered graphs ⋮ Automated conjecturing. I: Fajtlowicz's Dalmatian heuristic revisited ⋮ Forbidden subgraphs and the König-Egerváry property ⋮ How many attackers can selfish defenders catch? ⋮ 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 ⋮ Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids ⋮ A characterization of Konig-Egervary graphs using a common property of all maximum matchings ⋮ Crown reductions for the minimum weighted vertex cover problem ⋮ Fractionally total colouring \(G_{n,p}\) ⋮ On \(\alpha\)-critical edges in König--Egerváry graphs ⋮ Berge's theorem for the maximum charge problem ⋮ New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition ⋮ Regular graphs with equal matching number and independence number ⋮ On Duality between Local Maximum Stable Sets of a Graph and Its Line-Graph
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A characterization of the graphs in which the transversal number equals the matching number
- Ear-decompositions of matching-covered graphs
- Matching theory
- Independence numbers of graphs - an extension of the Koenig-Egervary theorem
- Minimum node covers and 2-bicritical graphs
- Node-weighted graphs having the König-Egerváry property
- Vertices Belonging to All or to No Maximum Stable Sets of a Graph
- Vertex packings: Structural properties and algorithms
- On the integer-valued variables in the linear vertex packing problem
- Paths, Trees, and Flowers
This page was built for publication: König-Egerváry graphs, 2-bicritical graphs and fractional matchings
