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

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

Authors: Felicia Lucke, F. Mann 

Publication date: 30 August 2022

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

zbMATH Keywords

clique numberindependence numberedge contractionvertex deletionblocker problems

Mathematics Subject Classification ID

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

Cites Work

• Network flows. Theory, algorithms, and applications.
• Blockers and transversals
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Title not available (Why is that?)
• Graph theory
• Intersection of longest paths in graph classes
• Reducing the chromatic number by vertex or edge deletions
• Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
• 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
• Minimum \(d\)-transversals of maximum-weight stable sets in trees
• Deleting vertices to bound path length

Cited In (2)

• Using Edge Contractions and Vertex Deletions to Reduce the Independence Number and the Clique Number
• Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2169976)