Clique-width and induced topological minors

Paweł Rafał Bieliński; Jadwiga Czyżewska; Martin Milanič; Amir Nikabadi; Paweł Rzążewski

doi:10.48550/arXiv.2605.15453

Clique-width and induced topological minors

Paweł Rafał Bieliński
, Jadwiga Czyżewska
, Martin Milanič
, Amir Nikabadi
, Paweł Rzążewski

Warsaw University of Technology
University of Warsaw
University of Primorska

Research output: Working paper › Preprint

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.

Original language	English
Publisher	arXiv
Number of pages	6
DOIs	https://doi.org/10.48550/arXiv.2605.15453
Publication status	Published - 14 May 2026

Access to Document

10.48550/arXiv.2605.15453Licence: CC BY

2605.15453v1Submitted manuscript, 359 KBLicence: CC BY

Cite this

@misc{d40d81d1258b4e06bab13c3f07f72edd,

title = "Clique-width and induced topological minors",

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\textasciitilde{}question of Dabrowski, Johnson, and Paulusma.",

keywords = "cs.DM, math.CO",

author = "Bieli{\'n}ski, \{Pawe{\l} Rafa{\l}\} and Jadwiga Czy{\.z}ewska and Martin Milani{\v c} and Amir Nikabadi and Pawe{\l} Rz{\c a}{\.z}ewski",

year = "2026",

month = may,

day = "14",

doi = "10.48550/arXiv.2605.15453",

language = "English",

publisher = "arXiv",

type = "WorkingPaper",

institution = "arXiv",

}

TY - UNPB

T1 - Clique-width and induced topological minors

AU - Bieliński, Paweł Rafał

AU - Czyżewska, Jadwiga

AU - Milanič, Martin

AU - Nikabadi, Amir

AU - Rzążewski, Paweł

PY - 2026/5/14

Y1 - 2026/5/14

N2 - 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.

AB - 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.

KW - cs.DM

KW - math.CO

U2 - 10.48550/arXiv.2605.15453

DO - 10.48550/arXiv.2605.15453

M3 - Preprint

BT - Clique-width and induced topological minors

PB - arXiv

ER -

Clique-width and induced topological minors

Abstract

Access to Document

Fingerprint

Cite this