The hardness of the independence and matching clutter of a graph

DOI10.7494/OpMath.2016.36.3.375zbMath1335.05131arXiv0903.4907MaRDI QIDQ2805262

V. L. Musoyan, Hovhannes Sargsyan, Vahan V. Mkrtchyan, Sasun Hambardzumyan

Publication date: 10 May 2016

Published in: Opuscula Mathematica (Search for Journal in Brave)

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

zbMATH Keywords

matchingindependent sethardnessmaximal matchingmaximal independent setclutter

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

A tight lower bound for the hardness of clutters

Cites Work

• Randomly matchable graphs

This page was built for publication: The hardness of the independence and matching clutter of a graph