Hitting subgraphs in P₄-tidy graphs

DOI10.1016/J.AMC.2019.01.074MaRDI QIDQ2010691zbMATH OpenOpenAlexFDO

Authors Boštjan Brešar, Tim Kos, R. Krivoš-Belluš, Gabriel Semanišin

Publication date 27 November 2019

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.amc.2019.01.074

zbMATH Keywords

\(k\)-path vertex coverdecycling number\(P_4\)-tidy graphhitting setquasi-spider

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Recommendations

• Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
• Neighborhood covering and independence on P₄-tidy graphs and tree-cographs
• Vertex Cover Gets Faster and Harder on Low Degree Graphs
• An FPT algorithm for the vertex cover \(P_4\) problem
• A fixed-parameter algorithm for the vertex cover \(P_3\) problem

Cites work

• scientific article; zbMATH DE number 1375569 (Why is no real title available?)
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• scientific article; zbMATH DE number 2192124 (Why is no real title available?)
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• A New Class of Brittle Graphs
• Complexity and algorithms for the connected vertex cover problem in 4-regular graphs
• Cycle lengths and chromatic number of graphs
• Decycling graphs
• Efficient algorithm for the vertex cover \(P_k\) problem on cacti
• Independent packings in structured graphs
• Minimum \(k\)-path vertex cover
• On Independent Circuits Contained in a Graph
• On a unique tree representation for \(P_ 4\)-extendible graphs
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• On the k-path vertex cover of some graph products
• On the vertex \(k\)-path cover
• Reducibility among combinatorial problems
• The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs
• The complexity of dissociation set problems in graphs
• The complexity of restricted spanning tree problems
• Total dominating sequences in trees, split graphs, and under modular decomposition

Cited in

(3)

• Approximation algorithm for minimum connected 3-path vertex cover
• 3-path vertex cover and dissociation number of hexagonal graphs
• Neighborhood covering and independence on P₄-tidy graphs and tree-cographs

This page was built for publication: Hitting subgraphs in \(P_4\)-tidy graphs

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