Blockers for the stability number and the chromatic number

DOI10.1007/s00373-013-1380-2zbMath1306.05051OpenAlexW2044825393MaRDI QIDQ489343

Cédric Bentz, Bernard Ries, Christophe Picouleau, Cristina Bazgan

Publication date: 20 January 2015

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-013-1380-2

zbMATH Keywords

split graphstability numberchromatic numberthreshold graphblockerbipartitegraph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Related Items (16)

Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases ⋮ Inverse chromatic number problems in interval and permutation graphs ⋮ Reducing the chromatic number by vertex or edge deletions ⋮ Contraction Blockers for Graphs with Forbidden Induced Paths ⋮ Reducing the vertex cover number via edge contractions ⋮ Reducing graph parameters by contractions and deletions ⋮ The complexity of blocking (semi)total dominating sets with edge contractions ⋮ Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions ⋮ Critical vertices and edges in \(H\)-free graphs ⋮ Unnamed Item ⋮ Contraction and deletion blockers for perfect graphs and \(H\)-free graphs ⋮ Reducing graph transversals via edge contractions ⋮ Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut ⋮ Complexity and algorithms for constant diameter augmentation problems ⋮ Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions ⋮ Using edge contractions to reduce the semitotal domination number

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
• Minimum \(d\)-blockers and \(d\)-transversals in graphs
• The most vital nodes with respect to independent set and vertex cover
• Matching interdiction
• On short paths interdiction problems: Total and node-wise limited interdiction
• Blockers and transversals
• Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
• The bondage number of a graph
• Deterministic network interdiction
• Complexity of determining the most vital elements for the \(p\)-median and \(p\)-center location problems
• \(d\)-transversals of stable sets and vertex covers in weighted bipartite graphs
• The path partition problem and related problems in bipartite graphs
• Crown reductions for the minimum weighted vertex cover problem
• Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures

This page was built for publication: Blockers for the stability number and the chromatic number