Few induced disjoint paths for H-free graphs

DOI10.1007/978-3-031-18530-4_7MaRDI QIDQ6166893zbMATH OpenOpenAlexFDO

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

Publication date 3 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-18530-4_7

zbMATH Keywords

\(H\)-free graphcomplexity dichotomyinduced disjoint paths

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Few induced disjoint paths 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

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
• Detecting fixed patterns in chordal graphs in polynomial time
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• 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
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• The (theta, wheel)-free graphs. IV: Induced paths and cycles
• The \(k\)-in-a-path problem for claw-free graphs

Cited in

(4)

• Few induced disjoint paths for \(H\)-free graphs
• 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

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 Q6166893)