83 citations · 606 across the 54 of their papers we have counts for
3 papers · 2 filters
Empty pentagons in point sets with collinearities
János Barát, Vida Dujmović, Gwenaël Joret +5
An empty pentagon in a point set P in the plane is a set of five points in P in strictly convex position with no other point of P in their convex hull. We prove that every finite s…
Nonrepetitive Colourings of Planar Graphs with Colours
Vida Dujmović, Fabrizio Frati, Gwenaël Joret +1
A vertex colouring of a graph is \emph{nonrepetitive} if there is no path for which the first half of the path is assigned the same sequence of colours as the second half. The \emp…
A linear-time algorithm for finding a complete graph minor in a dense graph
Vida Dujmović, Daniel J. Harvey, Gwenaël Joret +2
Let g(t) be the minimum number such that every graph G with average degree d(G) \geq g(t) contains a K_{t}-minor. Such a function is known to exist, as originally shown by Mader. K…