\textsc{MAX MIN} vertex cover and the size of Betti tables

DOI10.1007/s00026-020-00521-4zbMath1467.13031arXiv2002.02523OpenAlexW3122250340MaRDI QIDQ2660135

Takayuki Hibi, Huy Tái Hà

Publication date: 29 March 2021

Published in: Annals of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

regularityprojective dimensionmonomial idealchordal graphedge idealBetti tablegap-free graph\textsc{MAX MIN} independent set\textsc{MAX MIN} vertex coversquarefree monomial

Mathematics Subject Classification ID

Commutative rings defined by monomial ideals; Stanley-Reisner face rings; simplicial complexes (13F55) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Syzygies, resolutions, complexes and commutative rings (13D02) Combinatorial aspects of commutative algebra (05E40)

Related Items

The size of Betti tables of edge ideals arising from bipartite graphs, The size of Betti tables of edge ideals of clique corona graphs, Comparing invariants of toric ideals of bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• On the max min vertex cover problem
• Progress in commutative algebra 1. Combinatorics and homology
• Approximating the minimum maximal independence number
• A note on the size of minimal covers
• Cohen-Macaulay graphs
• Projective dimension, graph domination parameters, and independence complex homology
• Fast algorithms for min independent dominating set
• Characteristic-independence of Betti numbers of graph ideals
• Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers
• Non-vanishingness of Betti Numbers of Edge Ideals
• Sequentially Cohen-Macaulay edge ideals
• A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
• Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes