Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions

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

zbMATH Keywords

computational complexity; chromatic number; clique number; edge contraction; vertex deletion; subclasses of perfect graphs

Mathematics Subject Classification ID

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