Clique-width and induced topological minors

Paweł Rafał Bieliński †, Jadwiga Czyżewska ‡, Martin Milanič §, Amir Nikabadi ∗, Paweł Rzążewski ∥ · 2026

Read Clique-width and induced topological minors by Paweł Rafał Bieliński †, Jadwiga Czyżewska ‡, Martin Milanič §, Amir Nikabadi ∗, Paweł Rzążewski ∥ (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-15453.txt.

Introduction

Paweł Rafał Bieliński and four others prove a result about graph classes forbidding induced subdivisions of H. Such a class has bounded clique-width exactly when H is an induced subgraph of the four-vertex path, the paw, or the diamond. A paw is a four-clique minus two adjacent edges, and a diamond from a four-clique minus one edge. The characterization answers a question of Dabrowski, Johnson, and Paulusma. It pins down precisely which forbidden subdivisions keep clique-width bounded and which let it grow without limit.

Catalog record

CREATORPaweł Rafał Bieliński †, Jadwiga Czyżewska ‡, Martin Milanič §, Amir Nikabadi ∗, Paweł Rzążewski ∥
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE14215
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.15453

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Clique-width and induced topological minors Thanks: † Warsaw University of Technology, Poland. Supported by the National Science Centre grant 2024/54/E/ST6/00094. Thanks: ‡ University of Warsaw, Poland ( [email protected] ). Supported by Polish National Science Centre SONATA BIS-12 grant number 2022/46/E/ST6/00143. Thanks: § FAMNIT and IAM, University of Primorska, Slovenia ( [email protected] ). Supported in part by the Slovenian Research and Innovation Agency (I0-0035, research program P1-0285 and research projects J1-60012, J1-70035, J1-70046, and N1-0370) and by the research program CogniCom (0013103) at the University of Primorska. Thanks: ∗ IT University of Copenhagen, Denmark ( [email protected] ). Supported by the Independent Research Fund Denmark (DFF), grant agreement number 2098-00012B Thanks: ∥ Warsaw University of Technology, Poland ( [email protected] ). Supported by the National Science Centre grant 2024/54/E/ST6/00094. Paweł Rafał Bieliński †, Jadwiga Czyżewska ‡, Martin Milanič §, Amir Nikabadi ∗, Paweł Rzążewski ∥ Abstract . A P 4 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 H , the class of graphs with no induced subdivision of H H has bounded clique-width if and only if H H is an induced subgraph of P 4 P_{4} , the paw, or the diamond. This answers a question of Dabrowski, Johnson, and Paulusma. 1. Introduction Graph classes defined by excluding a fixed graph with respect to some containment relation form a central topic in structural graph theory. For the minor relation, the Grid-Minor Theorem of Robertson and Seymour [ 16 ] implies a complete characterization of the graphs H for which the class of H -minor-free graphs has bounded treewidth: this happens precisely when H is planar. Because of the pivotal role of treewidth in algorithmic graph theory, there have been numerous attempts, both successful and unsuccessful, to find similar theorems for other containment relations combined with an appropriate width parameter. The containment relation vertex-minors combined with rank-width [ 11 ] , immersions combined with tree-cut width [ 18 ] , and induced minors combined with tree-independence number [ 10 ] are such examples. On the other hand, generalizing the Grid-Minor Theorem to induced subgraphs is an active area of research. This line of work is developed in the series “Induced subgraphs and tree decompositions”, whose stated goal is to understand which induced subgraphs are unavoidable in graphs of large treewidth [ 1 , 4 , 3 ] . In this paper, we focus on the setting in which the containment relation is the induced topological minor relation and the width parameter is clique-width . Clique-width, denoted by \operatorname{cw} , has been studied extensively both in algorithmic and structural graph theory. It generalizes the aforementioned classical notion of treewidth , denoted by \operatorname{tw} , in the following sense: For every graph G , it holds that {\operatorname{cw}(G)=\mathcal{O}(2^{\operatorname{tw}(G)})} [ 6 ] , whereas no converse bound holds, since there are graphs of arbitrarily large treewidth and bounded clique-width (a graph class \mathcal{G} has bounded clique-width if there exists c\in\mathbb{N} such that \operatorname{cw}(G)\leq c for all G\in\mathcal{G} ). Dabrowski, Johnson, and Paulusma [ 7 ] posed the following problem: Problem 1 (Dabrowski, Johnson, and Paulusma [ 7 , Problem 4.34] ) . For which graphs H does the class of H -induced-topological-minor-free graphs have bounded clique-width? We give a complete characterization of classes of H -induced-topological-minor-free graphs of bounded clique-width, and thereby provide a solution to Problem 1 . In particular, we prove the following: Theorem 1.1 . Let H be a graph. Then, the class of H -induced-topological-minor-free graphs has bounded clique-width if and only if H is an induced subgraph of the P_{4} , the paw, or the diamond. The proof of Theorem 1.1 combines known characterizations for H -free graphs and H -induced-topological-minor-free graphs for particular graphs H , as well as the analogue of Theorem 1.1 for H -induced-minor-free graphs. Throughout the note, graphs have finite vertex sets, no loops, and no parallel edges. We use \mathbb{N} to denote the set of positive integers. We let [n]\coloneqq\{1,\dots,n\} for every n\in\mathbb{N} . Let G=(V,E) be a graph. A clique in G is a set of pairwise adjacent vertices. For X\subseteq V(G) , we denote the subgraph of G induced by X as G[X] , that is, G[X]=(X,\{uv\colon u,v\in X\mbox{ and }uv\in E\}) . We denote by N(X) vertices of G\setminus X with a neighbor in X , and N[X]=N(X)\cup X . We denote by \Delta(G) the maximum degree of G , that is, the maximum value of |N(\{v\})| over all v\in V . A graph is subcubic if its maximum degree is at most 3 and complete multipartite if it admits a partition of its vertex set such that two distinct vertices are adjacent if and only if they belong to distinct parts. Given two graphs G and H , the graph H is a subdivision of G if H can be obtained from G by a sequence of edge subdivisions, a topological minor of G if some subdivision of H is a subgraph of G , an induced minor of G if H can be obtained from G by a sequence of vertex deletions or edge contractions, and an induced topological minor of G if some subdivision of H is an induced subgraph of G (in which case we also say that G contains an induced subdivision of H ). If H can be obtained from G by a sequence of vertex deletions, edge deletions, and edge contractions, then H is said to be a minor of G . If G does not contain an induced subgraph isomorphic to H , then we say that G is H -free . Analogously, we say that G is H -topological-minor-free , H -induced-topological-minor-free , H -minor-free , or H -induced-minor-free , respectively. Similarly, we say that G is \mathcal{H} -free for a set \mathcal{H} of graphs if G is H -free for all H\in\mathcal{H} . Figure 1 . From left to right: the P_{4} , the gem, the paw, the diamond, the claw, and the fat-house. We let P_{n} and K_{n} denote the chordless path and the complete graph on n vertices. A diamond is a graph obtained from a K_{4} by removing one edge of the K_{4} . A paw is a graph obtained from a K_{4} by removing two adjacent edges of the K_{4} . A claw is a graph obtained from a paw by removing the edge between the two vertices of degree 2 . A fat-house is a graph obtained from a K_{4} by adding a vertex adjacent to exactly two vertices of the K_{4} . A gem is graph obtained from a P_{4} by adding a vertex adjacent to all vertices of the P_{4} . (See Figure 1 ). The (n\times m) -grid , denoted G_{n\times m} , is the graph with vertex set [n]\times[m] and edge set \{\{(i,j),(i,j+1)\}\colon i\in[n],j\in[m-1]\}\cup\{\{(i,j),(i+1,j)\}\colon i\in[n-1],j\in[m]\}. The ( k\times k )-wall for k\geq 3 , denoted W_{k\times k} , is the graph G obtained from the (k\times

Read the complete text