On lower bounds for the matching number of subcubic graphs

2014/06/27 by Haxell, Penny, Scott, Alex
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1406.7227

Abstract

We give a complete description of the set of triples (a,b,c) of real numbers with the following property. There exists a constant K such that a n₃ + b n₂ + c n₁ - K is a lower bound for the matching number of every connected subcubic graph G, where n_i denotes the number of vertices of degree i for each i.

Related

• A lower bound on the acyclic matching number of subcubic graphs
• Uniquely restricted matchings in subcubic graphs
• Induced Matchings in Subcubic Graphs
• Two lower bounds for maximum matching
• Tight lower bounds on the matching number in a graph with given maximum degree