30 citations · 90 across the 12 of their papers we have counts for
13 papers
3-Colouring Graphs Excluding a Fixed Minor
Vida Dujmović, Hussein Houdrouge, Pat Morin
We show that, for every fixed graph , every -vertex graph that excludes as a minor is -colourable with clustering . That is, there exists a function…
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…
Grids have Unbounded Anagram-Free Chromatic Number
Saman Bazarghani, Paz Carmi, Vida Dujmović +1
We show that anagram-free vertex colouring a square grid requires a number of colours that increases with . This answers an open question in Wilson's thesis and show…
Separating layered treewidth and row treewidth
Prosenjit Bose, Vida Dujmović, Mehrnoosh Javarsineh +2
Layered treewidth and row treewidth are recently introduced graph parameters that have been key ingredients in the solution of several well-known open problems. It follows from the…
Stack-number is not bounded by queue-number
Vida Dujmović, David Eppstein, Robert Hickingbotham +2
We describe a family of graphs with queue-number at most 4 but unbounded stack-number. This resolves open problems of Heath, Leighton and Rosenberg (1992) and Blankenship and Oporo…
Asymptotically Optimal Vertex Ranking of Planar Graphs
Prosenjit Bose, Vida Dujmović, Mehrnoosh Javarsineh +1
A (vertex) -ranking is a colouring of the vertices of a graph with integer colours so that for any path of length at most , $…
Two Results on Layered Pathwidth and Linear Layouts
Vida Dujmović, Pat Morin, Céline Yelle
Layered pathwidth is a new graph parameter studied by Bannister et al (2015). In this paper we present two new results relating layered pathwidth to two types of linear layouts. Ou…
Adjacency Labelling for Planar Graphs (and Beyond)
Vida Dujmović, Louis Esperet, Gwenaël Joret +3
We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an -vertex planar graph is assigned a -bit label and the lab…
Clustered 3-Colouring Graphs of Bounded Degree
Vida Dujmović, Louis Esperet, Pat Morin +2
A (not necessarily proper) vertex colouring of a graph has "clustering" if every monochromatic component has at most vertices. We prove that planar graphs with maximum degr…
Graph product structure for non-minor-closed classes
Vida Dujmović, Pat Morin, David R. Wood
Dujmović 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 res…