On graphs with no induced subdivision of \(K_4\)

DOI10.1016/j.jctb.2012.04.005zbMath1244.05148arXiv1309.1926MaRDI QIDQ444381

Frédéric Maffray, Benjamin Lévêque, Nicolas Trotignon

Publication date: 14 August 2012

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

induced subgraph; series-parallel graphs; structure theorem; polynomial-time recognition algorithm; subdivision of \(K_{4}\)

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

05C51: Graph designs and isomorphic decomposition

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Triangle-free intersection graphs of line segments with large chromatic number
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
• The strong perfect graph theorem
• Claw-free graphs. IV: Decomposition theorem
• Decomposition by clique separators
• An algorithm for finding clique cut-sets
• Graphs without odd holes, parachutes or proper wheels: A generalization of Meyniel graphs and of line graphs of bipartite graphs
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Topology of series-parallel networks
• Colouring series-parallel graphs
• The Recognition of Series Parallel Digraphs
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Dividing a Graph into Triconnected Components
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Depth-First Search and Linear Graph Algorithms
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• Detecting induced subgraphs