Few induced disjoint paths for H-free graphs

DOI10.1016/J.TCS.2022.10.024MaRDI QIDQ2098179zbMATH OpenOpenAlexFDO

Authors Barnaby Martin, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen

Publication date 17 November 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2203.03319

zbMATH Keywords

\(H\)-free graphcomplexity dichotomyinduced disjoint paths

Mathematics Subject Classification ID

Paths and cycles (05C38) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Few induced disjoint paths for \(H\)-free graphs
• Induced disjoint paths and connected subgraphs for H-free graphs
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Induced disjoint paths in claw-free graphs
• Induced disjoint paths in claw-free graphs
• Edge-disjoint paths in digraphs with bounded independence number

Cites work

• A linear time algorithm for the induced disjoint paths problem in planar graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Algorithms for finding an induced cycle in planar graphs and bounded genus graphs
• Chordless paths through three vertices
• Colouring H-free graphs of bounded diameter.
• Detecting fixed patterns in chordal graphs in polynomial time
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Graph minors. XIII: The disjoint paths problem
• scientific article; zbMATH DE number 4133491 (Why is no real title available?)
• Induced disjoint paths and connected subgraphs for H-free graphs
• Induced disjoint paths in circular-arc graphs in linear time
• Induced disjoint paths in claw-free graphs
• Mim-width. I. Induced path problems
• On the complexity of testing for odd holes and induced odd paths
• Parameterized complexity of independent set in H-free graphs
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Polynomial-time Algorithm for Maximum Weight Independent Set on P ₆ -free Graphs
• The (theta, wheel)-free graphs. IV: Induced paths and cycles
• The \(k\)-in-a-path problem for claw-free graphs

Cited in

(7)

• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Induced disjoint paths and connected subgraphs for H-free graphs
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• Induced paths in graphs without anticomplete cycles
• Few induced disjoint paths for \(H\)-free graphs
• Few Induced Disjoint Paths for H-Free Graphs
• Parameterizing path partitions

This page was built for publication: Few induced disjoint paths for \(H\)-free graphs

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