In a reduction sequence of a graph, vertices are successively identified until the graph has
one vertex. At each step, when identifying $ u $ and $ v $, each edge incident to exactly one …

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 …

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 …

We show that for every integer n⩾ 1 n\geqslant1, there exists a graph G n G_n with (1+ o (1))
n (1+o(1))n vertices and n 1+ o (1) n^1+o(1) edges such that every nn‐vertex planar graph is …

Stanislaw Ulam asked whether there exists a universal countable planar graph (that is, a
countable planar graph that contains every countable planar graph as a subgraph). J\'anos …

An adjacency labeling scheme for a given class of graphs is an algorithm that for every
graph G from the class, assigns bit strings (labels) to vertices of G so that for any two vertices …

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 …

This paper shows that $ K_t $-minor-free (and $ K_ {s, t} $-minor-free) graphs $ G $ are
subgraphs of products of a tree-like graph $ H $(of bounded treewidth) and a complete …

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 …

The\emph {Product Structure Theorem} for planar graphs (Dujmovi\'c et al.\\emph
{JACM},\textbf {67}(4): 22) states that any planar graph is contained in the strong product of a …