73 citations · 387 across the 61 of their papers we have counts for
27 papers · 1 filter
The grid-minor theorem revisited
Vida Dujmović, Robert Hickingbotham, Jędrzej Hodor +6
We prove that for every planar graph of treedepth , there exists a positive integer such that for every -minor-free graph , there exists a graph of treewidth a…
Proof of the Clustered Hadwiger Conjecture
Vida Dujmović, Louis Esperet, Pat Morin +1
Hadwiger's Conjecture asserts that every -minor-free graph is properly -colourable. We prove the following improper analogue of Hadwiger's Conjecture: for fixed , ev…
The Excluded Tree Minor Theorem Revisited
Vida Dujmović, Robert Hickingbotham, Gwenaël Joret +3
We prove that for every tree of radius , there is an integer such that every -minor-free graph is contained in for some graph with pathwidth at m…
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…
Sparse universal graphs for planarity
Louis Esperet, Gwenaël Joret, Pat Morin
We show that for every integer there exists a graph with vertices and edges such that every -vertex planar graph is isomorphic to a su…
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 , $…
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…
Queue Layouts of Graphs with Bounded Degree and Bounded Genus
Vida Dujmović, Pat Morin, David R. Wood
Motivated by the question of whether planar graphs have bounded queue-number, we prove that planar graphs with maximum degree have queue-number , which improves upon…
Every Collinear Set in a Planar Graph Is Free
Vida Dujmović, Fabrizio Frati, Daniel Gonçalves +2
We show that if a planar graph has a plane straight-line drawing in which a subset of its vertices are collinear, then for any set of points, , in the plane with $|X|=|S…
Dual Circumference and Collinear Sets
Vida Dujmović, Pat Morin
We show that, if a -vertex triangulation of maximum degree has a dual that contains a cycle of length , then has a non-crossing straight-line drawing in which…
Minor-closed graph classes with bounded layered pathwidth
Vida Dujmović, David Eppstein, Gwenaël Joret +2
We prove that a minor-closed class of graphs has bounded layered pathwidth if and only if some apex-forest is not in the class. This generalises a theorem of Robertson and Seymour,…
Anagram-Free Chromatic Number is not Pathwidth-Bounded
Paz Carmi, Vida Dujmović, Pat Morin
The anagram-free chromatic number is a new graph parameter introduced independently Kamčev, Łuczak, and Sudakov (2017) and Wilson and Wood (2017). In this note, we show that there…
More Turán-Type Theorems for Triangles in Convex Point Sets
Boris Aronov, Vida Dujmović, Pat Morin +2
We study the following family of problems: Given a set of points in convex position, what is the maximum number triangles one can create having these points as vertices while a…
Orthogonal Tree Decompositions of Graphs
Vida Dujmović, Gwenaël Joret, Pat Morin +2
This paper studies graphs that have two tree decompositions with the property that every bag from the first decomposition has a bounded-size intersection with every bag from the se…
New Bounds for Facial Nonrepetitive Colouring
Prosenjit Bose, Vida Dujmović, Pat Morin +1
We prove that the facial nonrepetitive chromatic number of any outerplanar graph is at most 11 and of any planar graph is at most 22.
On Obstacle Numbers
Vida Dujmović, Pat Morin
The obstacle number is a new graph parameter introduced by Alpert, Koch, and Laison (2010). Mukkamala etal (2012) show that there exist graphs with n vertices having obstacle numbe…
Layered Separators in Minor-Closed Graph Classes with Applications
Vida Dujmović, Pat Morin, David R. Wood
Graph separators are a ubiquitous tool in graph theory and computer science. However, in some applications, their usefulness is limited by the fact that the separator can be as lar…