Knocking out \(P_k\)-free graphs

DOI10.1016/j.dam.2015.04.010zbMath1316.05082OpenAlexW2280813015MaRDI QIDQ2352787

Anthony Stewart, Daniël Paulusma, Matthew Johnson

Publication date: 6 July 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.04.010

zbMATH Keywords

computational complexitycographssplit graphsHamilton cycleparallel knock-out schemes

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Eulerian and Hamiltonian graphs (05C45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Eliminating graphs by means of parallel knock-out schemes
• Completely separable graphs
• Path factors and parallel knock-out schemes of almost claw-free graphs
• Upper bounds and algorithms for parallel knock-out numbers
• Complement reducible graphs
• \(k\)-NLC graphs and polynomial algorithms
• Upper bounds to the clique width of graphs
• The computational complexity of the parallel knock-out problem
• Knocking Out P k -free Graphs
• A Linear Recognition Algorithm for Cographs
• A Combinatorial Decomposition Theory
• Parallel Knockouts in the Complete Graph
• Graph Classes: A Survey
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES

This page was built for publication: Knocking out \(P_k\)-free graphs