Knocking out P_k-free graphs

DOI10.1016/J.DAM.2015.04.010MaRDI QIDQ2352787zbMATH OpenOpenAlexFDO

Authors Matthew Johnson, Daniël Paulusma, Anthony Stewart

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 complexityHamilton cyclecographssplit graphsparallel knock-out schemes

Mathematics Subject Classification ID

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

Recommendations

• Knocking out \(P _{k }\)-free graphs
• Upper Bounds and Algorithms for Parallel Knock-Out Numbers
• Upper bounds and algorithms for parallel knock-out numbers
• The Computational Complexity of the Parallel Knock-Out Problem
• Mathematical Foundations of Computer Science 2004

Cites work

• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2044928 (Why is no real title available?)
• scientific article; zbMATH DE number 1472167 (Why is no real title available?)
• A Combinatorial Decomposition Theory
• A Linear Recognition Algorithm for Cographs
• Complement reducible graphs
• Completely separable graphs
• Eliminating graphs by means of parallel knock-out schemes
• Graph Classes: A Survey
• Knocking out \(P _{k }\)-free graphs
• On the clique-width of some perfect graph classes
• Parallel Knockouts in the Complete Graph
• Path factors and parallel knock-out schemes of almost claw-free graphs
• The computational complexity of the parallel knock-out problem
• Upper bounds and algorithms for parallel knock-out numbers
• Upper bounds to the clique width of graphs
• \(k\)-NLC graphs and polynomial algorithms

Cited in

(3)

• Knocking out \(P _{k }\)-free graphs
• Upper Bounds and Algorithms for Parallel Knock-Out Numbers
• A New Characterization of P_k-free Graphs

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

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