Tight bounds on maximal and maximum matchings
From MaRDI portal
Publication:1877645
DOI10.1016/j.disc.2004.05.003zbMath1044.05056OpenAlexW2042269609MaRDI QIDQ1877645
Rudolf Fleischer, Christian A. Duncan, Erik D. Demaine, Stephen G. Kobourov, Therese C. Biedl
Publication date: 19 August 2004
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2004.05.003
Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (45)
Edge guards for polyhedra in three-space ⋮ Positivity of the virial coefficients in lattice dimer models and upper bounds on the number of matchings on graphs ⋮ Secure wire shuffling in the probing model ⋮ A lower bound on the acyclic matching number of subcubic graphs ⋮ Index of parameters of iterated line graphs ⋮ On chordal and perfect plane near-triangulations ⋮ On line graphs of subcubic triangle-free graphs ⋮ Global forcing number for maximal matchings in corona products ⋮ Improved induced matchings in sparse graphs ⋮ Matchings in graphs of odd regularity and girth ⋮ Matching and edge-connectivity in regular graphs ⋮ On vertex independence number of uniform hypergraphs ⋮ A characterization of the subcubic graphs achieving equality in the Haxell‐Scott lower bound for the matching number ⋮ Bounding the mim‐width of hereditary graph classes ⋮ Smallest maximal matchings of graphs ⋮ Matching for Graphs of Bounded Degree ⋮ A Hall-type theorem with algorithmic consequences in planar graphs ⋮ Independent sets and matchings in subcubic graphs ⋮ Tight bound for matching ⋮ On the complexity and algorithm of grooming regular traffic in WDM optical networks ⋮ Game matching number of graphs ⋮ On the induced matching problem ⋮ Bounds on total domination in claw-free cubic graphs ⋮ Spanning Eulerian subgraphs of large size ⋮ Lower bounds on the uniquely restricted matching number ⋮ Bounding the Mim-Width of Hereditary Graph Classes. ⋮ A lower bound on the diameter of the flip graph ⋮ Maximal independent sets and maximal matchings in series-parallel and related graph classes ⋮ Tight lower bounds on the size of a maximum matching in a regular graph ⋮ Computing large matchings in planar graphs with fixed minimum degree ⋮ Paired-domination number of claw-free odd-regular graphs ⋮ Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree ⋮ A characterization of graphs with given maximum degree and smallest possible matching number ⋮ Matching and edge-connectivity in graphs with given maximum degree ⋮ Maximal independent sets and maximal matchings in series-parallel and related graph classes ⋮ Unnamed Item ⋮ A characterization of graphs with given maximum degree and smallest possible matching number. II ⋮ A tight lower bound on the matching number of graphs via Laplacian eigenvalues ⋮ Improved Induced Matchings in Sparse Graphs ⋮ Bounds on maximum \(b\)-matchings ⋮ The clique-transversal number of a \(\{K_{1, 3}, K_4 \}\)-free 4-regular graph ⋮ Unavoidable minors of large 4-connected bicircular matroids ⋮ A generalization of Petersen's matching theorem ⋮ On Lower Bounds for the Matching Number of Subcubic Graphs ⋮ Limitations of sums of bounded read formulas and ABPs
Cites Work
- Unnamed Item
- Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
- Lower bounds on the cardinality of the maximum matchings of planar graphs
- Bridges and Hamiltonian circuits in planar graphs
- Efficient Algorithms for Petersen's Matching Theorem
- TWO THEOREMS IN GRAPH THEORY
- Bipartite Edge Coloring in $O(\Delta m)$ Time
- On Representatives of Subsets
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- The Factorization of Linear Graphs
This page was built for publication: Tight bounds on maximal and maximum matchings
