pith. sign in

arxiv: 2605.15453 · v1 · pith:YLH3ZWZLnew · submitted 2026-05-14 · 💻 cs.DM · math.CO

Clique-width and induced topological minors

Pawe{\l} Rafa{\l} Bieli\'nski , Jadwiga Czy\.zewska , Martin Milani\v{c} , Amir Nikabadi , Pawe{\l} Rz\k{a}\.zewski This is my paper

Pith reviewed 2026-05-19 14:32 UTC · model grok-4.3

classification 💻 cs.DM math.CO
keywords clique-widthinduced subdivisionstopological minorsbounded clique-widthgraph classesforbidden induced structuresP4diamond
0
0 comments X

The pith

The class of graphs with no induced subdivision of H has bounded clique-width if and only if H is an induced subgraph of P4, the paw, or the diamond.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves a complete characterization of the graphs H for which forbidding induced subdivisions of H yields graph classes with bounded clique-width. This holds precisely when H is an induced subgraph of P4, the paw, or the diamond. A sympathetic reader cares because clique-width controls the existence of efficient algorithms for many graph problems, so the result draws a sharp line between cases where such algorithms are guaranteed and cases where they may not be. It settles an open question on the connection between induced topological minors and clique-width.

Core claim

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 P4, the paw, or the diamond.

What carries the argument

The if-and-only-if dichotomy on H, where H must be an induced subgraph of one of three small graphs (P4, paw, or diamond) to force bounded clique-width in all avoiding graphs.

If this is right

  • Avoiding induced subdivisions of P4, the paw, or the diamond produces classes where clique-width is bounded.
  • For every other H, explicit constructions exist of graphs with arbitrarily large clique-width that avoid any induced subdivision of H.
  • The result gives a full classification of single forbidden induced topological minors according to whether they bound clique-width.
  • Many NP-hard problems admit polynomial-time algorithms on the resulting bounded clique-width classes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar dichotomies might exist for related parameters such as rank-width or treewidth under the same forbidden structures.
  • The classification could guide the discovery of new hereditary classes with efficient algorithms for coloring or vertex cover.
  • One could test whether the unbounded cases exhibit clique-width growing at a particular rate, such as logarithmic in the number of vertices.

Load-bearing premise

The explicit constructions of graph families with unbounded clique-width that still avoid induced subdivisions of any H outside those three small graphs must hold.

What would settle it

Find any graph H that is not an induced subgraph of P4, the paw, or the diamond, yet every graph without an induced subdivision of H has clique-width bounded by some fixed constant.

Figures

Figures reproduced from arXiv: 2605.15453 by Amir Nikabadi, Jadwiga Czy\.zewska, Martin Milani\v{c}, Pawe{\l} Rafa{\l} Bieli\'nski, Pawe{\l} Rz\k{a}\.zewski.

Figure 1
Figure 1. Figure 1: From left to right: the P4, the gem, the paw, the diamond, the claw, and the fat-house. We let Pn and Kn denote the chordless path and the complete graph on n vertices. A diamond is a graph obtained from a K4 by removing one edge of the K4. A paw is [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The 5-by-5 square grid (left) and the 5-by-5 wall W5×5 (right). We will make use of the following fact about unboundedness of clique-width in the class of walls and their line graphs (we do not need the definition of clique-width in this paper). Observation 1.2. The class of walls has unbounded clique-width. The class of line graphs of walls has unbounded clique-width. We briefly justify Observation 1.2. T… view at source ↗
read the original abstract

A $P_4$ 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_4$, the paw, or the diamond. This answers a~question of Dabrowski, Johnson, and Paulusma.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript proves a dichotomy: for any fixed 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 P4, the paw, or the diamond. The 'if' direction follows from structural containment arguments showing that such H are contained in graphs whose induced-subdivision-free classes are known to have bounded clique-width; the 'only if' direction is established by explicit constructions, for every other H, of infinite families that avoid induced subdivisions of H yet contain large walls or grids and therefore have unbounded clique-width. This resolves a question of Dabrowski, Johnson, and Paulusma.

Significance. If the constructions are correct, the result supplies a complete, constructive characterization of when forbidding an induced topological minor bounds clique-width. This is valuable because clique-width governs the tractability of many MSO problems, and the paper supplies both the bounded cases and concrete unbounded families, making the dichotomy falsifiable and directly usable for further structural results. The explicit families constitute a clear strength.

minor comments (3)
  1. Introduction, paragraph 3: the statement that the three target graphs are the only ones whose induced-subdivision-free classes have bounded clique-width would be clearer if the authors briefly recall the known bounded-clique-width results for P4, paw, and diamond that are being invoked.
  2. Section 4 (constructions): several families are defined by successive attachments of paths or vertices; adding a short table that, for each minimal excluded H, lists the base graph, the unbounded minor used, and the key lemma showing absence of an induced subdivision of H would improve readability.
  3. Notation: the symbol for 'induced subdivision' is introduced in the abstract but first defined only in Section 2; moving the definition to the preliminaries or adding a forward reference would help.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, accurate summary of the main dichotomy result, and recommendation of minor revision. The significance noted regarding the explicit constructions and resolution of the question from Dabrowski, Johnson, and Paulusma is appreciated.

Circularity Check

0 steps flagged

No circularity: self-contained if-and-only-if characterization via explicit constructions

full rationale

The paper proves a standard graph-theoretic dichotomy: bounded clique-width for induced-subdivision-free classes holds precisely when H is an induced subgraph of one of three small graphs. The 'if' direction is a direct structural containment argument. The 'only if' direction is discharged by exhibiting, for each excluded H, an explicit infinite family of graphs that avoid induced subdivisions of H while containing known unbounded-clique-width substructures (e.g., walls or grids). These families are constructed independently of the target theorem and are not obtained by fitting parameters or by renaming the result itself. No self-citation is invoked as a load-bearing uniqueness theorem, and the work answers an external open question rather than closing a loop on its own inputs. The derivation therefore remains self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies entirely on standard graph-theoretic definitions and does not introduce new free parameters, ad-hoc axioms, or invented entities beyond the established notions of induced subdivisions and clique-width.

axioms (1)
  • standard math Standard definitions and properties of graphs, induced subgraphs, subdivisions, and clique-width as used in structural graph theory.
    The theorem statement presupposes these background concepts from the literature.

pith-pipeline@v0.9.0 · 5653 in / 1251 out tokens · 60364 ms · 2026-05-19T14:32:44.739707+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Induced subgraphs and tree decom- positions I

    Tara Abrishami, Maria Chudnovsky, and Kristina Vušković. Induced subgraphs and tree decom- positions I. Even-hole-free graphs of bounded degree.Journal of Combinatorial Theory, Series B, 157:144–175, 2022

    work page 2022

  2. [2]

    Induced minor free graphs: Isomorphism and clique-width.Algorithmica, 80(1):29–47, 2018

    Rémy Belmonte, Yota Otachi, and Pascal Schweitzer. Induced minor free graphs: Isomorphism and clique-width.Algorithmica, 80(1):29–47, 2018

    work page 2018

  3. [3]

    Induced subgraphs and tree decompositions XIX

    Maria Chudnovsky, Julien Codsi, Sepehr Hajebi, and Sophie Spirkl. Induced subgraphs and tree decompositions XIX. Thetas and forests.arXiv preprint, 2025.arXiv:2506.05602

    work page arXiv 2025

  4. [4]

    Induced subgraphs and tree decompositions XVI

    Maria Chudnovsky, Sepehr Hajebi, and Sophie Spirkl. Induced subgraphs and tree decompositions XVI. Complete bipartite induced minors.Journal of Combinatorial Theory, Series B, 176:287–318, 2026

    work page 2026

  5. [5]

    Excluding induced subdivisions of the bull and related graphs.Journal of Graph Theory, 71(1):49–68, 2012

    Maria Chudnovsky, Irena Penev, Alex Scott, and Nicolas Trotignon. Excluding induced subdivisions of the bull and related graphs.Journal of Graph Theory, 71(1):49–68, 2012

    work page 2012

  6. [6]

    Corneil and Udi Rotics

    Derek G. Corneil and Udi Rotics. On the relationship between clique-width and treewidth.SIAM Journal on Computing, 34(4):825–847, 2005

    work page 2005

  7. [7]

    Dabrowski, Matthew Johnson, and Daniël Paulusma.Clique-width for hereditary graph classes, page 1–56

    Konrad K. Dabrowski, Matthew Johnson, and Daniël Paulusma.Clique-width for hereditary graph classes, page 1–56. London Mathematical Society Lecture Note Series. Cambridge University Press, 2019

    work page 2019

  8. [8]

    Dabrowski and Daniël Paulusma

    Konrad K. Dabrowski and Daniël Paulusma. Clique-width of graph classes defined by two forbidden induced subgraphs.The Computer Journal, 59(5):650–666, 2016

    work page 2016

  9. [9]

    Treewidth versus clique number

    Clément Dallard, Martin Milanič, and Kenny Štorgel. Treewidth versus clique number. III. Tree- independence number of graphs with a forbidden structure.Journal of Combinatorial Theory, Series B, 167:338–391, 2024

    work page 2024

  10. [10]

    Treewidth versus clique number

    Clément Dallard, Martin Milanič, and Kenny Štorgel. Treewidth versus clique number. I. Graph classes with a forbidden structure.SIAM Journal on Discrete Mathematics, 35(4):2618–2646, 2021

    work page 2021

  11. [11]

    The grid theorem for vertex-minors

    Jim Geelen, O-joung Kwon, Rose McCarty, and Paul Wollan. The grid theorem for vertex-minors. Journal of Combinatorial Theory, Series B, 158:93–116, 2023. 6 CLIQUE-WIDTH AND INDUCED TOPOLOGICAL MINORS

    work page 2023

  12. [12]

    Line graphs of bounded clique-width.Discrete Mathematics, 307(22):2734–2754, 2007

    Frank Gurski. Line graphs of bounded clique-width.Discrete Mathematics, 307(22):2734–2754, 2007

    work page 2007

  13. [13]

    Lozin, and Martin Milanič

    Marcin Kamiński, Vadim V. Lozin, and Martin Milanič. Recent developments on graphs of bounded clique-width.Discrete Applied Mathematics, 157(12):2747–2761, 2009

    work page 2009

  14. [14]

    AndreaMunaro.Onlinegraphsofsubcubictriangle-freegraphs.Discrete Mathematics, 340(6):1210– 1226, 2017

    work page 2017

  15. [15]

    Tree width and tangles: a new connectivity measure and some applications.Surveys in combinatorics, 241:87–162, 1997

    Bruce Reed. Tree width and tangles: a new connectivity measure and some applications.Surveys in combinatorics, 241:87–162, 1997

    work page 1997

  16. [16]

    Neil Robertson and Paul D. Seymour. Graph minors. V. Excluding a planar graph.Journal of Combinatorial Theory, Series B, 41(1):92–114, 1986

    work page 1986

  17. [17]

    Rodica Boliac and Vadim V. Lozin. On the Clique-Width of Graphs in Hereditary Classes. In Algorithms and Computation, ISAAC 2002, volume 2518 ofLecture Notes in Computer Science, pages 44–54. Springer, 2002

    work page 2002

  18. [18]

    The structure of graphs not admitting a fixed immersion.Journal of Combinatorial Theory, Series B, 110:47–66, 2015

    Paul Wollan. The structure of graphs not admitting a fixed immersion.Journal of Combinatorial Theory, Series B, 110:47–66, 2015

    work page 2015