Publications with Michał T. Seweryn
Three-dimensional graph products with unbounded stack-number.
D. Eppstein, R. Robert Hickingbotham, L. Merker, S. Norin, M. T. Seweryn, and D. R. Wood.
arXiv:2202.05327.
Discrete Comput. Geom. 71: 1210–1237, 2024.The strong product of any three graphs of non-constant size has unbounded book thickness. In the case of strong products of three paths, and more generally of triangulations of \(n\times n\times n\) grid graphs obtained by adding a diagonal to each square of the grid, the book thickness is \(\Theta(n^{1/3})\). This is the first explicit example of a graph family with bounded maximum degree and unbounded book thickness.
Product structure extension of the Alon–Seymour–Thomas theorem.
M. Distel, V. Dujmović, D. Eppstein, R. Robert Hickingbotham, G. Joret, P. Micek, P. Morin, M. T. Seweryn, and D. R. Wood.
arXiv:2212.08739.
SIAM J. Discrete Math. 38 (3): 2095–2107, 2024.The graphs in any nontrivial minor-closed graph family can be represented as strong products of a graph of treewidth 4 with a clique of size \(O(\sqrt{n})\). For planar graphs and \(K_{3,t}\)-minor-free graphs, the treewidth can be reduced to 2.