30 citations · 90 across the 12 of their papers we have counts for
4 papers · 1 filter
Product structure extension of the Alon--Seymour--Thomas theorem
Marc Distel, Vida Dujmović, David Eppstein +6
Alon, Seymour and Thomas [1990] proved that every -vertex graph excluding as a minor has treewidth less than . Illingworth, Scott and Wood [2022] recently…
Bounded-Degree Planar Graphs Do Not Have Bounded-Degree Product Structure
Vida Dujmović, Gwenaël Joret, Piotr Micek +2
Product structure theorems are a collection of recent results that have been used to resolve a number of longstanding open problems on planar graphs and related graph classes. One…
Linear versus centred chromatic numbers
Prosenjit Bose, Vida Dujmović, Hussein Houdrouge +2
$\DeclareMathOperator{\chicen}{χ_{\mathrm{cen}}}\DeclareMathOperator{\chilin}{χ_{\mathrm{lin}}}$ A centred colouring of a graph is a vertex colouring in which every connected subgr…
Odd Colourings of Graph Products
Vida Dujmović, Pat Morin, Saeed Odak
The odd colouring number is a new graph parameter introduced by Petruševski and Škrekovski. In this note, we show that graphs with so called product structure have bounded odd-colo…