M. Seweryn

activity

20102023

most citedExcluding a ladder

5 citations · 12 across the 9 of their papers we have counts for

collaborators

Showing 2022Show all

3 papers · 1 filter

math.CO2022

Edge separators for graphs excluding a minor

Gwenaël Joret, William Lochet, Michał T. Seweryn

We prove that every $n$ -vertex $K_{t}$ -minor-free graph $G$ of maximum degree $Δ$ has a set $F$ of $O (t^{2} (lo g t)^{1/4} Δ n)$ edges such that every component of $G - F$ has at m…

math.CO2022★ 4 cited

Product structure extension of the Alon--Seymour--Thomas theorem

Marc Distel, Vida Dujmović, David Eppstein +6

Alon, Seymour and Thomas [1990] proved that every $n$ -vertex graph excluding $K_{t}$ as a minor has treewidth less than $t^{3/2} n$ . Illingworth, Scott and Wood [2022] recently…

math.CO2022★ 1 cited

Three-dimensional graph products with unbounded stack-number

David Eppstein, Robert Hickingbotham, Laura Merker +3

We prove that the stack-number of the strong product of three $n$ -vertex paths is $Θ (n^{1/3})$ . The best previously known upper bound was $O (n)$ . No non-trivial lower bound was kno…