8 papers
Lollipops, dense cycles and chords
ZdenÄk DvoÅák, Beatriz Martins, Stéphan Thomassé +1
In 1980, Gupta, Kahn and Robertson proved that every graph with minimum degree at least contains a cycle containing at least vertices each having at least $…
First Order Logic and Twin-Width in Tournaments and Dense Oriented Graphs
Colin Geniet, Stéphan Thomassé
We characterise the classes of tournaments with tractable first-order model checking. For every hereditary class of tournaments , first-order model checking is either f…
Small hitting sets for longest paths and cycles
Sergey Norin, Raphael Steiner, Stephan Thomassé +1
Motivated by an old question of Gallai (1966) on the intersection of longest paths in a graph and the well-known conjectures of Lovász (1969) and Thomassen (1978) on the maximum l…
A Polynomial-Time Approximation Algorithm for Complete Interval Minors
Romain Bourneuf, Julien Cocquet, Chaoliang Tang +1
As shown by Robertson and Seymour, deciding whether the complete graph is a minor of an input graph is a fixed parameter tractable problem when parameterized by . From…
A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number
Romain Bourneuf, Pierre Charbit, Stéphan Thomassé
In its Euclidean form, the Dense Neighborhood Lemma (DNL) asserts that if is a finite set of points of such that for each the ball intersects…
Two-block paths in oriented graphs of large semidegree
Irena Penev, S Taruni, Stéphan Thomassé +2
We study the existence of oriented paths with two blocks in oriented graphs under semidegree conditions. A block of an oriented path is a maximal directed subpath. Given positive i…