Detecting induced subgraphs
From MaRDI portal
Publication:5900072
DOI10.1016/j.endm.2007.07.036zbMath1341.05169arXiv1309.0971MaRDI 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
05C83: Graph minors
05C85: Graph algorithms (graph-theoretic aspects)
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Related Items
Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Induced Disjoint Paths in Claw-Free Graphs, A structure theorem for graphs with no cycle with a unique chord and its consequences, Finding an induced subdivision of a digraph, 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, MIP formulations for induced graph optimization problems: a tutorial, Graph editing to a fixed target, Complete intersection toric ideals of oriented graphs and chorded-theta subgraphs, On graphs with no induced subdivision of \(K_4\), Detecting an induced net subdivision, Finding a subdivision of a digraph, CIO and ring graphs: deficiency and testing, The \(k\)-in-a-tree problem for graphs of girth at least \(k\), Partial characterizations of circle graphs, Clique or hole in claw-free graphs, Containment relations in split graphs, The four-in-a-tree problem in triangle-free graphs, Finding induced trees, Induced disjoint paths in AT-free graphs, Few induced disjoint paths for \(H\)-free graphs, The (theta, wheel)-free graphs. IV: Induced paths and cycles, Detecting fixed patterns in chordal graphs in polynomial time, Detecting an induced subdivision of \(K_{4}\), Finding induced paths of given parity in claw-free graphs, The \(k\)-in-a-path problem for claw-free graphs, Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
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