Hitting subgraphs in P₄-tidy graphs

DOI10.1016/J.AMC.2019.01.074zbMATH Open1428.05254OpenAlexW2911678318MaRDI QIDQ2010691FDOQ2010691

R. Krivoš-Belluš, Tim Kos, Boštjan Brešar, 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

Recommendations

• Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
• Neighborhood covering and independence on \(P_4\)-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

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)

Cites Work

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

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_4\)-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)