Reducing graph parameters by contractions and deletions

DOI10.1007/s00453-023-01141-zarXiv2210.10503OpenAlexW4383652941MaRDI QIDQ6119833

F. Mann, Felicia Lucke

Publication date: 25 March 2024

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2210.10503

zbMATH Keywords

independence numberchromatic numberclique numberedge contractionvertex deletionedge deletionblocker problems

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Blockers for the stability number and the chromatic number
• Blockers and transversals
• Complement reducible graphs
• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• Blocking total dominating sets via edge contractions
• Reducing the domination number of \(( P_3 + k P_2 )\)-free graphs via one edge contraction
• Reducing the chromatic number by vertex or edge deletions
• Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
• Deleting vertices to bound path length
• The pathwidth and treewidth of cographs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Intersection of longest paths in graph classes