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

DOI10.1016/j.jctb.2012.04.005zbMath1244.05148arXiv1309.1926OpenAlexW4291166258MaRDI 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 subgraphseries-parallel graphsstructure theorempolynomial-time recognition algorithmsubdivision of \(K_{4}\)

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph designs and isomorphic decomposition (05C51)

Related Items (24)

Using SPQR-trees to speed up algorithms based on 2-cutset decompositions ⋮ Graph editing to a fixed target ⋮ The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs ⋮ The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring ⋮ The chromatic number of graphs with no induced subdivision of \(K_4\) ⋮ Detecting an induced subdivision of \(K_{4}\) ⋮ Edge-colouring and total-colouring chordless graphs ⋮ Acyclic chromatic index of chordless graphs ⋮ The chromatic number of {ISK4, diamond, bowtie}‐free graphs ⋮ Some remarks on graphs with no induced subdivision of \(K_4\) ⋮ Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs ⋮ Amalgams and χ-Boundedness ⋮ Burling graphs revisited. III: Applications to \(\chi \)-boundedness ⋮ Chromatic number of ISK4-free graphs ⋮ Characterizing and generalizing cycle completable graphs ⋮ Stable sets in \(\{\mathrm{ISK4,wheel}\}\)-free graphs ⋮ On Triangle-Free Graphs That Do Not Contain a Subdivision of the Complete Graph on Four Vertices as an Induced Subgraph ⋮ Strongly unichord-free graphs ⋮ Using SPQR-trees to speed up recognition algorithms based on 2-cutsets ⋮ Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings ⋮ Induced disjoint paths in AT-free graphs ⋮ Wheel-free planar graphs ⋮ Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs ⋮ Restricted frame graphs and a conjecture of Scott

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

This page was built for publication: On graphs with no induced subdivision of \(K_4\)