Hitting subgraphs in \(P_4\)-tidy graphs

DOI10.1016/j.amc.2019.01.074zbMath1428.05254OpenAlexW2911678318MaRDI QIDQ2010691

Rastislav Krivoš-Belluš, Tim Kos, Boštjan Brešar, Gabriel Semanisin

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)

Related Items

Approximation algorithm for minimum connected 3-path vertex cover ⋮ 3-path vertex cover and dissociation number of hexagonal graphs

Cites Work

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