Abstract
We prove that for every planar graph X of treedepth h, there exists a positive integer c such that for every X-minor-free graph G, there exists a graph H of treewidth at most f(h) such that G is isomorphic to a subgraph of H ✉ Kc. This is a qualitative strengthening of the Grid-Minor Theorem of Robertson and Seymour (JCTB, 1986), and treedepth is the optimal parameter in such a result. As an example application, we use this result to improve the upper bound for weak coloring numbers of graphs excluding a given graph as a minor.
Original language | English |
---|---|
Pages | 1241-1245 |
Number of pages | 5 |
DOIs | |
Publication status | Published - 2024 |
Event | Annual ACM-SIAM Symposium on Discrete Algorithms, 2024 - Westin Alexandria Old Town, Alexandria, United States of America Duration: 7 Jan 2024 → 10 Jan 2024 Conference number: 35th https://www.siam.org/conferences/cm/conference/soda24 |
Conference
Conference | Annual ACM-SIAM Symposium on Discrete Algorithms, 2024 |
---|---|
Abbreviated title | SODA 2024 |
Country/Territory | United States of America |
City | Alexandria |
Period | 7/01/24 → 10/01/24 |
Internet address |