View in EDS

PRODUCT STRUCTURE EXTENSION OF THE ALON-SEYMOUR-THOMAS THEOREM.

Saved in:
Bibliographic Details
Title: PRODUCT STRUCTURE EXTENSION OF THE ALON-SEYMOUR-THOMAS THEOREM.
Authors: DISTEL, MARC1 marc.distel@monash.edu, DUJMOVIĆ, VIDA2 vida.dujmovic@uottawa.ca, EPPSTEIN, DAVID3 eppstein@uci.edu, HICKINGBOTHAM, ROBERT1 robert.hickingbotham@monash.edu, JORET, GWENAËL4 gwenael.joret@ulb.be, MICEK, PIOTR5 piotr.micek@uj.edu.pl, MORIN, PAT6 morin@scs.carleton.ca, SEWERYN, MICHAŁ T.4 michal.seweryn@ulb.be, WOOD, DAVID R.1 david.wood@monash.edu
Source: SIAM Journal on Discrete Mathematics. 2024, Vol. 38 Issue 3, p2095-2107. 13p.
Subjects: Problem solving, Mathematics
Abstract: Alon, Seymour and Thomas [[J. Amer. Math. Soc., 3 (1990), pp. 801-808]] proved that every n-vertex graph excluding Kt as a minor has treewidth less than t3/2√n. Illingworth, Scott and Wood [2022] recently refined this result by showing that every such graph is a subgraph of some graph with treewidth t - 2, where each vertex is blown up by a complete graph of order Ϭ(√tn). Solving an open problem of Illingworth, Scott and Wood [2022], we prove that the treewidth bound can be reduced to 4 while keeping blowups of order Ϭt(√n). As an extension of the Lipton-Tarjan theorem, in the case of planar graphs, we show that the treewidth can be further reduced to 2, which is best possible. We generalise this result for K3,t-minor-free graphs, with blowups of order Ϭ(t√n). This setting includes graphs embeddable on any fixed surface. [ABSTRACT FROM AUTHOR]
Copyright of SIAM Journal on Discrete Mathematics is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:Alon, Seymour and Thomas [[J. Amer. Math. Soc., 3 (1990), pp. 801-808]] proved that every n-vertex graph excluding Kt as a minor has treewidth less than t3/2√n. Illingworth, Scott and Wood [2022] recently refined this result by showing that every such graph is a subgraph of some graph with treewidth t - 2, where each vertex is blown up by a complete graph of order Ϭ(√tn). Solving an open problem of Illingworth, Scott and Wood [2022], we prove that the treewidth bound can be reduced to 4 while keeping blowups of order Ϭt(√n). As an extension of the Lipton-Tarjan theorem, in the case of planar graphs, we show that the treewidth can be further reduced to 2, which is best possible. We generalise this result for K3,t-minor-free graphs, with blowups of order Ϭ(t√n). This setting includes graphs embeddable on any fixed surface. [ABSTRACT FROM AUTHOR]
ISSN:08954801
DOI:10.1137/23M1591773