8 papers
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…
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 le…
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…
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 $…
A structural description of Zykov and Blanche Descartes graphs
Malory Marin, Stéphan Thomassé, Nicolas Trotignon +1
In 1949, Zykov proposed the first explicit construction of triangle-free graphs with arbitrarily large chromatic number. We define a Zykov graph as any induced subgraph of a graph…
On the complexity of Client-Waiter and Waiter-Client games
Valentin Gledel, Nacim Oijid, Sébastien Tavenas +1
Positional games were introduced by Hales and Jewett in 1963, and their study became more popular after Erdos and Selfridge's first result on their connection to Ramsey theory and…
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…