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

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

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)

Cites Work

• Title not available (Why is that?)
• Blockers and transversals
• Deterministic network interdiction
• The bondage number of a graph
• Title not available (Why is that?)
• The path partition problem and related problems in bipartite graphs
• Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
• Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
• The most vital nodes with respect to independent set and vertex cover
• Title not available (Why is that?)
• Matching interdiction
• On short paths interdiction problems: Total and node-wise limited interdiction
• Crown reductions for the minimum weighted vertex cover problem
• 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
• Minimum \(d\)-blockers and \(d\)-transversals in graphs
• \(d\)-transversals of stable sets and vertex covers in weighted bipartite graphs

Cited In (19)

• Using edge contractions to reduce the semitotal domination number
• Blocking independent sets for \(H\)-free graphs via edge contractions and vertex deletions
• On blockers and transversals of maximum independent sets in co-comparability graphs
• Critical vertices and edges in \(H\)-free graphs
• Reducing the vertex cover number via edge contractions
• Title not available (Why is that?)
• Complexity of stability
• Reducing the chromatic number by vertex or edge deletions
• Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases
• Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
• Contraction Blockers for Graphs with Forbidden Induced Paths
• Inverse chromatic number problems in interval and permutation graphs
• Reducing graph transversals via edge contractions
• Distance-preserving graph compression techniques
• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut
• Complexity and algorithms for constant diameter augmentation problems
• 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)