M. Seweryn

activity

20102023

most citedExcluding a ladder

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

collaborators

Showing math.COShow all

8 papers · 1 filter

math.CO2023

Powers of planar graphs, product structure, and blocking partitions

Marc Distel, Robert Hickingbotham, Michał T. Seweryn +1

We prove that the $k$ -power of any planar graph $G$ is contained in $H ⊠ P ⊠ K_{f (Δ (G), k)}$ for some graph $H$ with bounded treewidth, some path $P$ , and some functio…

math.CO2023

Pathwidth vs cocircumference

Marcin Briański, Gwenaël Joret, Michał T. Seweryn

The {\em circumference} of a graph $G$ with at least one cycle is the length of a longest cycle in $G$ . A classic result of Birmelé (2003) states that the treewidth of $G$ is at mo…

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…

math.CO2020

Erdős-Hajnal properties for powers of sparse graphs

Marcin Briański, Piotr Micek, Michał Pilipczuk +1

We prove that for every nowhere dense class of graphs $C$ , positive integer $d$ , and $ε > 0$ , the following holds: in every $n$ -vertex graph $G$ from $\mathcal{C}…

math.CO2020★ 5 cited

Excluding a ladder

Tony Huynh, Gwenaël Joret, Piotr Micek +2

A ladder is a $2 \times k$ grid graph. When does a graph class $C$ exclude some ladder as a minor? We show that this is the case if and only if all graphs $G$ in $\mathca…

math.CO2019

Improved bound for the dimension of posets of treewidth two

Michał T. Seweryn

Joret et al. proved that posets with cover graphs of treewidth at most 2 have dimension at most 1276. Their proof is long and very complex. We give a short and much simpler proof t…