2 citations · 3 across the 4 of their papers we have counts for
9 papers · 1 filter
Powers of paths in tournaments
Nemanja Draganić, François Dross, Jacob Fox +7
In this short note we prove that every tournament contains the -th power of a directed path of linear length. This improves upon recent results of Yuster and of Girão. We also g…
A Polynomial Time Algorithm for the -Disjoint Shortest Paths Problem
William Lochet
The disjoint paths problem is a fundamental problem in algorithmic graph theory and combinatorial optimization. For a given graph and a set of pairs of terminals in , it…
A Polynomial Kernel for Paw-Free Editing
Eduard Eiben, William Lochet, Saket Saurabh
For a fixed graph , the -free-editing problem asks whether we can modify a given graph by adding or deleting at most edges such that the resulting graph does not cont…
Progress on the adjacent vertex distinguishing edge colouring conjecture
Gwenaël Joret, William Lochet
A proper edge colouring of a graph is adjacent vertex distinguishing if no two adjacent vertices see the same set of colours. Using a clever application of the Local Lemma, Hatami…
Immersion of transitive tournaments in digraphs with large minimum outdegree
W. Lochet
We prove the existence of a function such that every simple digraph with minimum outdegree greater than contains an immersion of the transitive tournament on vert…
A proof of the Erdős-Sands-Sauer-Woodrow conjecture
N. Bousquet, W. Lochet, S. Thomassé
A very nice result of Bárány and Lehel asserts that every finite subset or can be covered by -boxes (i.e. each box has two antipodal points in ). As…