Blockers for the stability number and the chromatic number

DOI10.1007/S00373-013-1380-2zbMATH Open1306.05051OpenAlexW2044825393MaRDI QIDQ489343FDOQ489343

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

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

chromatic numbersplit graphblockerthreshold graphstability numberbipartitegraph

Mathematics Subject Classification ID

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

Recommendations

• On the chromatic vertex stability number of graphs
• On the chromatic edge stability number of graphs
• Reducing the chromatic number by vertex or edge deletions
• Critical graphs for the chromatic edge-stability number
• Nordhaus-Gaddum and other bounds for the chromatic edge-stability number

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1194938 (Why is no real title available?)
• scientific article; zbMATH DE number 871953 (Why is no real title available?)
• Blockers and transversals
• Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
• Complexity of determining the most vital elements for the \(p\)-median and \(p\)-center location problems
• Complexity of most vital nodes for independent set in graphs related to tree structures
• Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
• Crown reductions for the minimum weighted vertex cover problem
• Deterministic network interdiction
• Matching interdiction
• Minimum \(d\)-blockers and \(d\)-transversals in graphs
• On short paths interdiction problems: Total and node-wise limited interdiction
• The bondage number of a graph
• The most vital nodes with respect to independent set and vertex cover
• The path partition problem and related problems in bipartite graphs
• \(d\)-transversals of stable sets and vertex covers in weighted bipartite graphs

Cited in

(20)

• Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases
• Blocking independent sets for \(H\)-free graphs via edge contractions and vertex deletions
• Contraction Blockers for Graphs with Forbidden Induced Paths
• Reducing graph transversals via edge contractions
• On blockers and transversals of maximum independent sets in co-comparability graphs
• Distance-preserving graph compression techniques
• Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
• Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut
• Reducing the vertex cover number via edge contractions
• When removing an independent set is optimal for reducing the chromatic number
• Complexity and algorithms for constant diameter augmentation problems
• Complexity of stability
• Reducing the chromatic number by vertex or edge deletions
• Inverse chromatic number problems in interval and permutation graphs
• Reducing graph transversals via edge contractions
• Critical vertices and edges in \(H\)-free graphs
• Using edge contractions to reduce the semitotal domination number
• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• The complexity of blocking (semi)total dominating sets with edge contractions
• Reducing graph parameters by contractions and deletions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q489343)