On graphs with no induced subdivision of $K_4$

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 $\mathcal{C}$ 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 $\mathcal{C}$ is 3-colorable and entails a polynomial-time recognition algorithm for membership in $\mathcal{C}$. As an intermediate result, we prove a structure theorem for the graphs whose cycles are all chordless.

References in corpus (2)

• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Detecting induced subgraphs

Cited by in corpus (12)

• Edge-colouring and total-colouring chordless graphs
• Graphs that do not contain a cycle with a node that has at least two neighbors on it
• The (theta, wheel)-free graphs Part I: only-prism and only-pyramid graphs
• On triangle-free graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph
• Wheel-free planar graphs
• Triangle-free graphs that do not contain an induced subdivision of $K_4$ are 3-colorable
• The (theta, wheel)-free graphs Part III: cliques, stable sets and coloring
• Acyclic Chromatic Index of Chordless Graphs
• Burling graphs revisited, part III: Applications to $\chi$-boundedness
• Stable sets in {ISK4,wheel}-free graphs
• Induced subgraphs and tree decompositions VI. Graphs with 2-cutsets
• Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs