Few induced disjoint paths for \(H\)-free graphs

DOI10.1007/978-3-031-18530-4_7zbMath1528.90224OpenAlexW4312500484MaRDI QIDQ6166893

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

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

complexity dichotomy\(H\)-free graphinduced disjoint paths

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• 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é
• On the complexity of testing for odd holes and induced odd paths
• Graph minors. XIII: The disjoint paths problem
• Induced disjoint paths in AT-free graphs
• Mim-width. I. Induced path problems
• The (theta, wheel)-free graphs. IV: Induced paths and cycles
• Detecting fixed patterns in chordal graphs in polynomial time
• The \(k\)-in-a-path problem for claw-free graphs
• Induced disjoint paths in circular-arc graphs in linear time
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Induced Disjoint Paths in Claw-Free Graphs
• Detecting induced subgraphs
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs

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