Blocker size via matching minors

DOI10.1016/j.disc.2018.04.004zbMath1388.05147arXiv1606.06263OpenAlexW2962894117MaRDI QIDQ1637141

Nikola Yolov

Publication date: 7 June 2018

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

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

zbMATH Keywords

transversalsinduced matchingset coverblockermaximal independent setclutter\(k\)-SATclutter minor

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Transversal (matching) theory (05D15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

HYPE: a system of hyperintensional logic (with an application to semantic paradoxes)

Cites Work

• On generating all maximal independent sets
• On diameters and radii of bridged graphs
• Zero knowledge and the chromatic number
• On graphs with polynomially solvable maximum-weight clique problem
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• An upper bound on the number of cliques in a graph
• An upper bound for the number of maximal independent sets in a graph
• On cliques in graphs
• Unnamed Item