A simple layered-wheel-like construction

Maria Chudnovsky †∗, David Fischer †, Sepehr Hajebi ‡, Sophie Spirkl ‡§, Bartosz Walczak ∥ · 2025

Read A simple layered-wheel-like construction by Maria Chudnovsky †∗, David Fischer †, Sepehr Hajebi ‡, Sophie Spirkl ‡§, Bartosz Walczak ∥ (2025) 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-2507-06169.txt.

Introduction

Maria Chudnovsky and four co-authors give, in a 2025 paper, a simpler way to build a family of graphs that block a major open problem. The problem asks which graphs must appear inside any graph of large treewidth. Past work narrowed the blockers to layered wheel-like graphs, but every known way to build them was intricate.

Their construction is plain, yet reaches any treewidth desired. High-degree points can be pushed far apart, the shortest cycle can be made as long as wanted, and a certain outerstring part always keeps small treewidth. No older construction had all three traits at once. The graphs also give the first counterexample, with large girth available, to a conjecture of Trotignon about such blockers.

Catalog record

CREATORMaria Chudnovsky †∗, David Fischer †, Sepehr Hajebi ‡, Sophie Spirkl ‡§, Bartosz Walczak ∥
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-06169

Browse the full library · About the Tower of Babel

Full text

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

A simple layered-wheel-like construction Thanks: † Princeton University, Princeton, NJ, USA Thanks: ‡ Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada Thanks: ∗ Supported by NSF Grant DMS-2348219 and AFOSR grant FA9550-22-1-0083. Thanks: § We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), [funding reference number RGPIN-2020-03912]. Cette recherche a été financée par le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG), [numéro de référence RGPIN-2020-03912]. This project was funded in part by the Government of Ontario. This research was conducted while Spirkl was an Alfred P. Sloan Fellow. Thanks: ∥ Department of Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland. Partially supported by the National Science Center of Poland grant 2019/34/E/ST6/00443. Maria Chudnovsky †∗, David Fischer †, Sepehr Hajebi ‡, Sophie Spirkl ‡§, Bartosz Walczak ∥ Abstract . In recent years, there has been significant interest in characterizing the induced subgraph obstructions to bounded treewidth and pathwidth. While this has recently been resolved for pathwidth, the case of treewidth remains open, and prior work has reduced the problem to understanding the layered-wheel-like obstructions – graphs that contain large complete minor models with each branching set inducing a path, exclude large walls as induced minors, exclude large complete bipartite graphs as induced minors, and exclude large complete subgraphs. There are various constructions of such graphs, but they are all rather involved. In this paper, we present a simple construction of layered-wheel-like graphs with arbitrarily large treewidth. Three notable features of our construction are: (a) the vertices of degree at least four can be made arbitrarily far apart; (b) the girth can be made arbitrarily large; and (c) every outerstring induced subgraph of the graphs from our construction has treewidth bounded by an absolute constant. In contrast, among several previously known constructions of layered wheels, none achieves (a); at most one satisfies either (b) or (c); and none satisfies both (b) and (c) simultaneously. In particular, this is related to a former conjecture of Trotignon, that every graph with large enough treewidth, excluding large walls and large complete bipartite graphs as induced minors, and large complete subgraphs, must contain an outerstring induced subgraph of large treewidth. Our construction provides the first counterexample to this conjecture that can also be made to have arbitrarily large girth. 1. Introduction 1.1. Background and the main result Graphs in this paper have finite vertex sets, no loops and no parallel edges. Let G=(V(G),E(G)) be a graph. A graph H is a minor of G if H is isomorphic to a graph that can be obtained from G by a series of vertex deletions, edge deletions, and edge contractions, and H is an induced minor of G if H is isomorphic to a graph that can be obtained from G by a series of vertex deletions and edge contractions (and deleting the loops and the parallel edges produced in the contraction process). A tree decomposition (T,\chi) of G consists of a tree T and a map \chi\colon V(T)\to 2^{V(G)} such that the following hold. • For every vertex v\in V(G) , there exists t\in V(T) such that v\in\chi(t) . • For every edge v_{1}v_{2}\in E(G) , there exists t\in V(T) such that v_{1},v_{2}\in\chi(t) . • For every v\in V(G) , the subgraph of T induced by \{t\in V(T)\colon v\in\chi(t)\} is connected. For a tree decomposition (T,\chi) of G with V(T)=\{t_{1},\ldots,t_{n}\} , the sets \chi(t_{1}),\ldots,\chi(t_{n}) are called the bags of (T,\chi) . The width of (T,\chi) is defined as \max_{t\in V(T)}|\chi(t)|-1 . The treewidth of G , denoted by \tw(G) , is the minimum width of a tree decomposition of G . The Grid Theorem of Robertson and Seymour, Theorem 1.1 below, fully describes the unavoidable subgraphs of graphs with large treewidth. For every k\in\mathbb{N} , the (k\times k) -wall , denoted by W_{k\times k} , is a planar graph with maximum degree three and with treewidth k (see Figure 1 ; a precise definition can be found in [ 2 ] ). Every subdivision of W_{k\times k} is also a graph of treewidth k . Theorem 1.1 (Robertson and Seymour [ 21 ] ) . There is a function f\colon\mathbb{N}\rightarrow\mathbb{N} such that every graph of treewidth at least f(k) contains a subdivision of W_{k\times k} as a subgraph. Figure 1. W_{5\times 5} Theorem 1.1 also holds if “subgraph” is replaced by “minor” (in that case “subdivision” will not be necessary anymore). Recently, there has been growing interest in understanding the unavoidable induced subgraphs of graphs with large treewidth. For instance, subdivided walls, complete graphs, and complete bipartite graphs are easily observed to have arbitrarily large treewidth. Line graphs of subdivided walls form another family of graphs with unbounded treewidth (recall that the line graph L(F) of a graph F is the graph with vertex set E(F) , such that two vertices of L(F) are adjacent if the corresponding edges of G share an end). Since these four types of graphs do not contain each other as induced subgraphs, they must all be included in any potential family of induced subgraph obstructions to bounded treewidth; hence, they are often referred to as the “basic obstructions”. A full characterization of the induced subgraph obstructions to bounded treewidth remains unknown. Specifically, there are various constructions [ 5 , 7 , 8 , 9 , 10 , 12 , 14 , 19 , 22 ] showing that forbidding the basic obstructions as induced subgraphs does not guarantee bounded treewidth. Also, a recent result of Alecu, Bonnet, Villafana and Trotignon [ 5 ] shows that the only hereditary set of obstructions that can be forbidden (as induced subgraphs) from a graph class in order to guarantee bounded treewidth is the family of all graphs (a graph class is hereditary if it is closed under taking induced subgraphs). Theorem 1.2 (Alecu, Bonnet, Villafana, Trotignon [ 5 ] ) . For every t\in\mathbb{N} , there is a hereditary graph class \mathcal{C}_{t} of unbounded treewidth and a constant c_{t} such that, for any graph H of treewidth at most t , every graph G\in\mathcal{C}_{t} not containing H as an induced subgraph has treewidth at most c_{t} . On the other hand, we now know that every non-basic obstruction falls in one of only two categories: those that are “complete bipartite induced minor models” and those that are “linear complete minor models”. Let us define these terms precisely. Given a graph G , a model in G is a graph H with vertex set \{X_{1},\ldots,X_{n}\} such that the following hold. (i) For all i with 1\leq i\leq n , we have X_{i}\subseteq V(G) and G[X_{i}] is connected. (ii) For all i and j with 1\leq i<j\leq n , we have X_{i}\cap X_{j}=\varnothing . (iii) For all i and j with 1\leq i<j\leq n , if X_{i} and X_{j} are adjacent in H , then there exist v_{i}\in X_{i} and v_{j}\in X_{j} such that v_{i}v_{j}\in E(G) . We say that the model H in G is linear if G[X_{i}] is path for all i with 1\leq i\leq n , and that H is induced if the converse to ( iii ) is also true; that is, for all

Read the complete text