73 citations · 785 across the 86 of their papers we have counts for
4 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…
Excluded Forest Minors and the Erdős-Pósa Property
Samuel Fiorini, Gwenaël Joret, David R. Wood
A classical result of Robertson and Seymour states that the set of graphs containing a fixed planar graph as a minor has the so-called Erdős-Pósa property; namely, there exists…
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…