Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
From MaRDI portal
Publication:2835660
DOI10.1007/978-3-319-45587-7_4zbMath1432.05074MaRDI QIDQ2835660
Bernard Ries, Daniël Paulusma, Christophe Picouleau
Publication date: 30 November 2016
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: http://dro.dur.ac.uk/19879/1/19879.pdf
computational complexity; chromatic number; clique number; edge contraction; vertex deletion; subclasses of perfect graphs
90C35: Programming involving graphs or networks
68R10: Graph theory (including graph drawing) in computer science
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
Unnamed Item, When removing an independent set is optimal for reducing the chromatic number, Reducing graph parameters by contractions and deletions, Critical vertices and edges in \(H\)-free graphs, 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, Using edge contractions and vertex deletions to reduce the independence number and the clique number, Reducing the domination number of graphs via edge contractions and vertex deletions, Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut, Reducing the chromatic number by vertex or edge 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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- The strong perfect graph theorem
- Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
- Paw-free graphs
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- Contraction Blockers for Graphs with Forbidden Induced Paths
- Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures
- Minimum vertex blocker clique problem