On blockers and transversals of maximum independent sets in co-comparability graphs

DOI10.1016/j.dam.2024.06.020zbMATH Open1544.05091MaRDI QIDQ6585269

Bernard Ries, Felicia Lucke

Publication date: 9 August 2024

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

zbMATH Keywords

independence numbervertex deletiontransversal problemsco-comparability graphsblocker problems

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Transversal (matching) theory (05D15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum edge blocker dominating set problem
• Minimum \(d\)-blockers and \(d\)-transversals in graphs
• The most vital nodes with respect to independent set and vertex cover
• Blockers for the stability number and the chromatic number
• A simple version of Karzanov's blocking flow algorithm
• Blockers and transversals
• Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• Blocking total dominating sets via edge contractions
• Using edge contractions to reduce the semitotal domination number
• Reducing the domination number of graphs via edge contractions and vertex deletions
• Reducing the domination number of \(( P_3 + k P_2 )\)-free graphs via one edge contraction
• \(d\)-transversals of stable sets and vertex covers in weighted bipartite graphs
• Reducing the chromatic number by vertex or edge deletions
• Distance-hereditary graphs are clique-perfect
• Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
• Deleting vertices to bound path length
• Minimum vertex blocker clique problem
• Intersection of longest paths in graph classes
• Assistance and interdiction problems on interval graphs
• Reducing graph parameters by contractions and deletions

This page was built for publication: On blockers and transversals of maximum independent sets in co-comparability graphs