73 citations · 785 across the 86 of their papers we have counts for
5 papers · 2 filters
Erdős-Pósa from ball packing
Wouter Cames van Batenburg, Gwenaël Joret, Arthur Ulmer
A classic theorem of Erdős and Pósa (1965) states that every graph has either vertex-disjoint cycles or a set of vertices meeting all its cycles. While the standa…
Large independent sets in triangle-free cubic graphs: beyond planarity
Wouter Cames van Batenburg, Jan Goedgebeur, Gwenaël Joret
Every -vertex planar triangle-free graph with maximum degree at most has an independent set of size at least . This was first conjectured by Albertson, Bollobá…
Revisiting a theorem by Folkman on graph colouring
Marthe Bonamy, Pierre Charbit, Oscar Defrain +5
We give a short proof of the following theorem due to Jon H. Folkman (1969): The chromatic number of any graph is at most plus the maximum over all subgraphs of the difference…
Planar graphs have bounded nonrepetitive chromatic number
Vida Dujmović, Louis Esperet, Gwenaël Joret +2
A colouring of a graph is "nonrepetitive" if for every path of even order, the sequence of colours on the first half of the path is different from the sequence of colours on the se…
Unavoidable minors for graphs with large -dimension
Samuel Fiorini, Tony Huynh, Gwenaël Joret +1
A metric graph is a pair , where is a graph and is a distance function. Let be fixed. An isometric embedding of the met…