On graphs with no induced subdivision of K₄

DOI10.1016/J.JCTB.2012.04.005zbMATH Open1244.05148arXiv1309.1926OpenAlexW4291166258MaRDI QIDQ444381FDOQ444381

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

Publication date: 14 August 2012

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

Abstract: We prove a decomposition theorem for graphs that do not contain a subdivision of $K_4$ as an induced subgraph where $K_4$ is the complete graph on four vertices. We obtain also a structure theorem for the class $calC$ of graphs that contain neither a subdivision of $K_4$ nor a wheel as an induced subgraph, where a wheel is a cycle on at least four vertices together with a vertex that has at least three neighbors on the cycle. Our structure theorem is used to prove that every graph in $calC$ is 3-colorable and entails a polynomial-time recognition algorithm for membership in $calC$. As an intermediate result, we prove a structure theorem for the graphs whose cycles are all chordless.

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

Recommendations

• On Triangle-Free Graphs That Do Not Contain a Subdivision of the Complete Graph on Four Vertices as an Induced Subgraph
• Triangle-free graphs that do not contain an induced subdivision of \(K_4\) are 3-colorable
• The chromatic number of graphs with no induced subdivision of \(K_4\)
• The structure of (theta, pyramid, 1-wheel, 3-wheel)-free graphs
• Detecting an induced subdivision of \(K_{4}\)

zbMATH Keywords

induced subgraphstructure theoremseries-parallel graphspolynomial-time recognition algorithmsubdivision of \(K_{4}\)

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• Title not available (Why is that?)
• Triangle-free intersection graphs of line segments with large chromatic number
• Depth-First Search and Linear Graph Algorithms
• Title not available (Why is that?)
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
• Decomposition by clique separators
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Title not available (Why is that?)
• The strong perfect graph theorem
• The Recognition of Series Parallel Digraphs
• Dividing a Graph into Triconnected Components
• Topology of series-parallel networks
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Claw-free graphs. IV: Decomposition theorem
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• 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
• Colouring series-parallel graphs

Cited In (35)

• The chromatic number of graphs with no induced subdivision of \(K_4\)
• Restricted frame graphs and a conjecture of Scott
• Induced regular perfect graphs
• Burling graphs revisited. III: Applications to \(\chi \)-boundedness
• Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs
• On Triangle-Free Graphs That Do Not Contain a Subdivision of the Complete Graph on Four Vertices as an Induced Subgraph
• The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
• Some remarks on graphs with no induced subdivision of \(K_4\)
• Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs
• Totally odd \(K_4\)-subdivisions in 4-chromatic graphs
• Using SPQR-trees to speed up recognition algorithms based on 2-cutsets
• The chromatic number of {ISK4, diamond, bowtie}‐free graphs
• Characterizing and generalizing cycle completable graphs
• Title not available (Why is that?)
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Using SPQR-trees to speed up algorithms based on 2-cutset decompositions
• Excluding 4-wheels
• Graphs with no induced \(C_ 4\) and \(2K_ 2\)
• Nonseparating K₄‐subdivisions in graphs of minimum degree at least 4
• Wheel-free planar graphs
• Induced subgraphs and tree decompositions. VI: Graphs with 2-cutsets
• Amalgams and \(\chi\)-boundedness
• Detecting an induced subdivision of \(K_4\)
• Graph editing to a fixed target
• Strongly unichord-free graphs
• The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring
• Graphs without \(K_ 4\) and well-quasi-ordering
• Chromatic number of ISK4-free graphs
• The structure of graphs with forbidden induced \(C_4\), \(\overline{C}_4\), \(C_5\), \(S_3\), chair and co-chair
• Detecting an induced subdivision of \(K_{4}\)
• Triangle-free graphs that do not contain an induced subdivision of \(K_4\) are 3-colorable
• Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
• Acyclic chromatic index of chordless graphs
• Stable sets in \(\{\mathrm{ISK4,wheel}\}\)-free graphs
• Edge-colouring and total-colouring chordless graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q444381)