Graph product structure theory expresses certain graphs as subgraphs of the strong product
of much simpler graphs. In particular, an elegant formulation for the corresponding structural …

Hadwiger's Conjecture asserts that every K_h-minor-free graph is properly (h-1)-colourable.
We prove the following improper analogue of Hadwiger's Conjecture: for fixed h, every K_h …

Abstract Dujmović, Joret, Micek, Morin, Ueckerdt and Wood [J. ACM 2020] proved that for
every planar graph $ G $ there is a graph $ H $ with treewidth at most 8 and a path $ P …

Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomass\'e and
Watrigant [FOCS 2020]. Very briefly, its essence is a gradual reduction (a contraction …

The planar graph product structure theorem of Dujmović et al.[J. ACM, 67 (2020), 22] states
that every planar graph is a subgraph of the strong product of a graph with bounded …

Product structure of graph classes with bounded treewidth Page 1 Combinatorics, Probability
and Computing (2023), 1–26 doi:10.1017/S0963548323000457 ARTICLE Product structure of …

For any small positive real ε and integer t> 1 ε, we build a graph with a vertex deletion set of
size t to a tree, and twin-width greater than 2 (1− ε) t. In particular, this shows that the twin …

Dujmovic, Joret, Micek, Morin, Ueckerdt and Wood [J. ACM 2020] proved that for every
graph G with Euler genus g there is a graph H with treewidth at most 4 and a path P such …

Dujmovi\'c et al.[\emph {J.~ ACM}~'20] recently proved that every planar graph is isomorphic
to a subgraph of the strong product of a bounded treewidth graph and a path. Analogous …

We give essentially tight bounds for, ν (d, k), the maximum number of distinct
neighbourhoods on a set X of k vertices in a graph with twin-width at most d. Using the …