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

DOI10.1007/978-3-319-45587-7_4zbMath1432.05074OpenAlexW2513523599MaRDI 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 complexitychromatic numberclique numberedge contractionvertex deletionsubclasses of perfect graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (13)

Using edge contractions and vertex deletions to reduce the independence number and the clique number ⋮ Reducing the chromatic number by vertex or edge deletions ⋮ When removing an independent set is optimal for reducing the chromatic number ⋮ Reducing graph parameters by contractions and deletions ⋮ The complexity of blocking (semi)total dominating sets with edge contractions ⋮ Reducing the domination number of graphs via edge contractions and vertex deletions ⋮ 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 ⋮ Blocking total dominating sets via edge contractions ⋮ Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut ⋮ Using edge contractions to reduce the semitotal domination number

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

This page was built for publication: Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions