David R. Wood

activity

20242026

collaborators

Showing math.COShow all

3 papers · 1 filter

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…