David R. Wood

activity

20242026

collaborators

4 papers

cs.DM2026

Adjacency labelling for proper minor-closed graph classes

Vida Dujmović, Cyril Gavoille, Gwenaël Joret +3

We show that every proper minor-closed class of graphs admits a $(1 + o (1)) lo g_{2} n$ -bit adjacency labelling scheme. Equivalently, for every proper minor-closed class $G$ a…

math.CO2025

3-Colouring Planar Graphs

Vida Dujmović, Pat Morin, Sergey Norin +1

We show that every $n$ -vertex planar graph is 3-colourable with monochromatic components of size $O (n^{4/9})$ . The best previous bound was $O (n^{1/2})$ due to Linial, Matoušek, She…

math.CO2024

Planar graphs in blowups of fans

Marc Distel, Vida Dujmović, Gwenaël Joret +3

We show that every $n$ -vertex planar graph is contained in the graph obtained from a fan by blowing up each vertex by a complete graph of order $O (n lo g^{2} n)$ . Equivalently,…

math.CO2024

Grid Minors and Products

Vida Dujmović, Pat Morin, David R. Wood +1

Motivated by recent developments regarding the product structure of planar graphs, we study relationships between treewidth, grid minors, and graph products. We show that the Carte…