Clique-width and induced topological minors

2026/05/14 by Paweł Rafał Bieliński, Jadwiga Czyżewska, Martin Milanič +2 · 1 voice
Computer Science · Mathematics · #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.2605.15453

Abstract

A P₄ is a chordless path on four vertices. A diamond is a graph obtained from a clique of size four by removing one edge of the clique. A paw is a graph obtained from a clique of size four by removing two adjacent edges of the clique. We prove that for a graph H, the class of graphs with no induced subdivision of H has bounded clique-width if and only if H is an induced subgraph of P₄, the paw, or the diamond. This answers a~question of Dabrowski, Johnson, and Paulusma.

Citations

• Induced subgraphs and tree decompositions XIX. Thetas and forests
• Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure
• Induced subgraphs and tree decompositions I. Even-hole-free graphs of bounded degree
• Treewidth versus clique number. I. Graph classes with a forbidden structure
• Induced Minor Free Graphs: Isomorphism and Clique-width
• Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs
• The structure of graphs not admitting a fixed immersion
• Excluding induced subdivisions of the bull and related graphs
• Line graphs of bounded clique-width
• Graph minors. V. Excluding a planar graph

Discussions

• Pawe{\l} Rafa{\l} Bieli\'nski, Jadwiga Czy\.zewska, Martin Milani\v{c}, Amir Nikabadi, Pawe{\l} Rz\k{a}\.zewski: Clique-width and induced topological minors https://arxiv.org/abs/2605.15453 https://ar [bsky, 0 points, 0 comments]

Related

• Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs
• Graphs without even holes or diamonds
• Treewidth versus clique number: induced minors
• Infinitely many minimal classes of graphs of unbounded clique-width
• Rank-width and tree-width of H-minor-free graphs