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

DOI10.1007/978-3-031-06678-8_30MaRDI QIDQ2169976zbMATH OpenOpenAlexFDO

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

• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Blockers and transversals
• Blocking total dominating sets via edge contractions
• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• Deleting vertices to bound path length
• Graph theory
• Intersection of longest paths in graph classes
• Minimum \(d\)-transversals of maximum-weight stable sets in trees
• Network flows. Theory, algorithms, and applications.
• Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
• Reducing the chromatic number by vertex or edge deletions
• Reducing the domination number of ( P₃ + k P₂ )-free graphs via one edge contraction

Cited in

(2)

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

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)