On Lower Bounds for the Matching Number of Subcubic Graphs

DOI10.1002/JGT.22063zbMath1365.05228arXiv1406.7227OpenAlexW2964138348MaRDI QIDQ5272918

Penny E. Haxell, Alexander D. Scott

Publication date: 5 July 2017

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1406.7227

zbMATH Keywords

matchingpolyhedronsubcubic graph

Mathematics Subject Classification ID

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

Related Items (7)

A complete description of convex sets associated with matchings and edge‐connectivity in graphs ⋮ A characterization of the subcubic graphs achieving equality in the Haxell‐Scott lower bound for the matching number ⋮ A characterization of graphs with given maximum degree and smallest possible matching number ⋮ Matching and edge-connectivity in graphs with given maximum degree ⋮ 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 ⋮ A generalization of Petersen's matching theorem

Uses Software

• Unnamed Item

Cites Work

• Unnamed Item
• Independent sets and matchings in subcubic graphs
• Small transversals in hypergraphs
• Tight bounds on maximal and maximum matchings
• Tight lower bounds on the size of a maximum matching in a regular graph
• Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree

This page was built for publication: On Lower Bounds for the Matching Number of Subcubic Graphs