Independent sets and matchings in subcubic graphs

DOI10.1016/j.disc.2012.03.002zbMath1244.05177OpenAlexW1996640753MaRDI QIDQ427833

Christian Löwenstein, Michael A. Henning, Dieter Rautenbach

Publication date: 18 June 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2012.03.002

zbMATH Keywords

independence numberchromatic numbermatching number\(\chi \)-binding function

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Related Items (20)

Bounded clique cover of some sparse graphs ⋮ Transversals and independence in linear hypergraphs with maximum degree two ⋮ A lower bound on the acyclic matching number of subcubic graphs ⋮ On line graphs of subcubic triangle-free graphs ⋮ Triangle packings and transversals of some \(K_{4}\)-free graphs ⋮ Matchings in graphs of odd regularity and girth ⋮ 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 ⋮ An optimal χ‐bound for (P6, diamond)‐free graphs ⋮ Independence and matching number in graphs with maximum degree 4 ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ Paired-domination number of claw-free odd-regular graphs ⋮ A characterization of graphs with given maximum degree and smallest possible matching number ⋮ Matching and edge-connectivity in graphs with given maximum degree ⋮ The Fano Plane and the Strong Independence Ratio in Hypergraphs of Maximum Degree 3 ⋮ 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 ⋮ The clique-transversal number of a \(\{K_{1, 3}, K_4 \}\)-free 4-regular graph ⋮ A generalization of Petersen's matching theorem ⋮ On Lower Bounds for the Matching Number of Subcubic Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Claw-free graphs. VI: Colouring
• The independence number in graphs of maximum degree three
• Linear chromatic bounds for a subfamily of \(3K_{1}\)-free graphs
• A note on Ramsey numbers
• Tight bounds on maximal and maximum matchings
• 11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)
• Tight lower bounds on the size of a maximum matching in a regular graph
• Independence, odd girth, and average degree
• Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Maximum matching and a polyhedron with 0,1-vertices
• A new proof of the independence ratio of triangle-free cubic graphs

This page was built for publication: Independent sets and matchings in subcubic graphs