4 papers
On a tree-based variant of bandwidth and forbidding simple topological minors
Hugo Jacob, William Lochet, Christophe Paul
We obtain structure theorems for graphs excluding a fan (a path with a universal vertex) or a dipole () as a topological minor. The corresponding decompositions can be com…
Robust Contraction Decomposition for Minor-Free Graphs and its Applications
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov +6
We prove a robust contraction decomposition theorem for -minor-free graphs, which states that given an -minor-free graph and an integer , one can partition in polynomi…
Blow-ups and extensions of trees in tournaments
Pierre Aboulker, Frédéric Havet, William Lochet +3
A class of acyclic digraphs is linearly unavoidable if there exists a constant such that every digraph is contained in all tournaments of order…
Packing Short Cycles
Matthias Bentert, Fedor V. Fomin, Petr A. Golovach +6
Cycle packing is a fundamental problem in optimization, graph theory, and algorithms. Motivated by recent advancements in finding vertex-disjoint paths between a specified set of v…