Using edge contractions and vertex deletions to reduce the independence number and the clique number

DOI10.1007/978-3-031-06678-8_30OpenAlexW4285238822MaRDI QIDQ2169976

F. Mann, Felicia Lucke

Publication date: 30 August 2022

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

zbMATH Keywords

independence numberclique numberedge contractionvertex deletionblocker problems

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Blockers and transversals
• 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
• Graph Theory
• Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
• Deleting vertices to bound path length
• 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

This page was built for publication: Using edge contractions and vertex deletions to reduce the independence number and the clique number