Publication:5900072

DOI10.1016/j.endm.2007.07.036zbMath1341.05169arXiv1309.0971OpenAlexW2180172454MaRDI QIDQ5900072

Benjamin Lévêque, David Y. Lin, Nicolas Trotignon, Frédéric Maffray

Publication date: 5 June 2008

Published in: Discrete Applied Mathematics, Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

inducedsubgraphsdetecting

Mathematics Subject Classification ID

Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (28)

The four-in-a-tree problem in triangle-free graphs ⋮ Graph editing to a fixed target ⋮ Complete intersection toric ideals of oriented graphs and chorded-theta subgraphs ⋮ The \(k\)-in-a-tree problem for graphs of girth at least \(k\) ⋮ Detecting an induced subdivision of \(K_{4}\) ⋮ Induced disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Induced disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ Finding induced paths of given parity in claw-free graphs ⋮ The \(k\)-in-a-path problem for claw-free graphs ⋮ On graphs with no induced subdivision of \(K_4\) ⋮ Partial characterizations of circle graphs ⋮ Detecting an induced net subdivision ⋮ Finding an induced subdivision of a digraph ⋮ Structural results on circular-arc graphs and circle graphs: a survey and the main open problems ⋮ The (theta, wheel)-free graphs. IV: Induced paths and cycles ⋮ Finding a subdivision of a digraph ⋮ CIO and ring graphs: deficiency and testing ⋮ Detecting fixed patterns in chordal graphs in polynomial time ⋮ Finding induced trees ⋮ Few induced disjoint paths for \(H\)-free graphs ⋮ Induced Disjoint Paths in Claw-Free Graphs ⋮ A structure theorem for graphs with no cycle with a unique chord and its consequences ⋮ Induced disjoint paths in AT-free graphs ⋮ Clique or hole in claw-free graphs ⋮ Containment relations in split graphs ⋮ Few induced disjoint paths for \(H\)-free graphs ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure

Cites Work

• Unnamed Item
• Unnamed Item
• The three-in-a-tree problem
• Finding and counting given length cycles
• On the complexity of testing for odd holes and induced odd paths
• Corrigendum to: On the complexity of testing for odd holes and induced odd paths
• Recognizing Berge graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Algorithms for Square-3PC($\cdot, \cdot$)-Free Berge Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Algorithms for Perfectly Contractile Graphs

This page was built for publication: Detecting induced subgraphs