# Stéphan Thomassé

According to our database1, Stéphan Thomassé authored at least 102 papers between 1997 and 2020.

Collaborative distances:
• Dijkstra number2 of four.
• Erdős number3 of two.

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2020
On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five.
SIAM J. Discret. Math., 2020

Twin-width III: Max Independent Set and Coloring.
CoRR, 2020

Twin-width II: small classes.
CoRR, 2020

Twin-width I: tractable FO model checking.
CoRR, 2020

(Theta, triangle)-free and (even hole, K<sub>4</sub>)-free graphs. Part 2 : bounds on treewidth.
CoRR, 2020

Parameterized Complexity of Independent Set in H-Free Graphs.
Algorithmica, 2020

Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in <i>H</i>-free graphs.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

An Algorithmic Weakening of the Erdős-Hajnal Conjecture.
Proceedings of the 28th Annual European Symposium on Algorithms, 2020

2019
Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems.
ACM Trans. Algorithms, 2019

Coloring tournaments: From local to global.
J. Comb. Theory, Ser. B, 2019

A proof of the Erdős-Sands-Sauer-Woodrow conjecture.
J. Comb. Theory, Ser. B, 2019

Separation Choosability and Dense Bipartite Induced Subgraphs.
Comb. Probab. Comput., 2019

Maximum independent sets in (pyramid, even hole)-free graphs.
CoRR, 2019

Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs.
CoRR, 2019

Convexly independent subsets of Minkowski sums of convex polygons.
CoRR, 2019

Subdivisions in Digraphs of Large Out-Degree or Large Dichromatic Number.
Electron. J. Comb., 2019

Edge-Partitioning a Graph into Paths: Beyond the Barát-Thomassen Conjecture.
Comb., 2019

The Independent Set Problem Is FPT for Even-Hole-Free Graphs.
Proceedings of the 14th International Symposium on Parameterized and Exact Computation, 2019

When Maximum Stable Set Can Be Solved in FPT Time.
Proceedings of the 30th International Symposium on Algorithms and Computation, 2019

2018
Multicut Is FPT.
SIAM J. Comput., 2018

Domination in tournaments.
J. Comb. Theory, Ser. B, 2018

Edge-decomposing graphs into coprime forests.
CoRR, 2018

Domination and Fractional Domination in Digraphs.
Electron. J. Comb., 2018

Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

EPTAS for Max Clique on Disks and Unit Balls.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017
A proof of the Barát-Thomassen conjecture.
J. Comb. Theory, Ser. B, 2017

Decomposing graphs into paths and trees.
Electron. Notes Discret. Math., 2017

Coloring dense digraphs.
Electron. Notes Discret. Math., 2017

Additive bases and flows in graphs.
Electron. Notes Discret. Math., 2017

A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs.
Algorithmica, 2017

On the Complexity of Partial Derivatives.
Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

2016
Isolating Highly Connected Induced Subgraphs.
SIAM J. Discret. Math., 2016

The Erdös-Hajnal Conjecture for Long Holes and Antiholes.
SIAM J. Discret. Math., 2016

Perfect graphs of arbitrarily large clique-chromatic number.
J. Comb. Theory, Ser. B, 2016

Linear kernel for Rooted Triplet Inconsistency and other problems based on conflict packing technique.
J. Comput. Syst. Sci., 2016

2015
Identifying Codes in Hereditary Classes of Graphs and VC-Dimension.
SIAM J. Discret. Math., 2015

The Erdős-Hajnal conjecture for paths and antipaths.
J. Comb. Theory, Ser. B, 2015

A $$\tau$$ τ -Conjecture for Newton Polygons.
Found. Comput. Math., 2015

Excluding clocks.
Electron. Notes Discret. Math., 2015

VC-dimension and Erdős-Pósa property.
Discret. Math., 2015

2014
Hitting and Harvesting Pumpkins.
SIAM J. Discret. Math., 2014

Parameterized Domination in Circle Graphs.
Theory Comput. Syst., 2014

Disjoint 3-Cycles in Tournaments: A Proof of The Bermond-Thomassen Conjecture for Tournaments.
Journal of Graph Theory, 2014

Satisfying more than half of a system of linear equations over GF(2): A multivariate approach.
J. Comput. Syst. Sci., 2014

Clique versus independent set.
Eur. J. Comb., 2014

Graphs with large chromatic number induce $3k$-cycles.
CoRR, 2014

The Erdős-Hajnal Conjecture for Long Holes and Anti-holes.
CoRR, 2014

A Note on the Minimum Distance of Quantum LDPC Codes.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

2013
A counterexample to a conjecture of Schwartz.
Soc. Choice Welf., 2013

Tournaments and colouring.
J. Comb. Theory, Ser. B, 2013

A linear vertex kernel for maximum internal spanning tree.
J. Comput. Syst. Sci., 2013

Oriented trees in digraphs.
Discret. Math., 2013

Parameterized algorithm for weighted independent set problem in bull-free graphs.
CoRR, 2013

A tau-conjecture for Newton polygons.
CoRR, 2013

Graph coloring, communication complexity and the stubborn problem (Invited talk).
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

2012
Cyclic orderings and cyclic arboricity of matroids.
J. Comb. Theory, Ser. B, 2012

Packing and Covering Triangles in K 4-free Planar Graphs.
Graphs Comb., 2012

A stability theorem on fractional covering of triangles by edges.
Eur. J. Comb., 2012

Scott's Induced Subdivision Conjecture for Maximal Triangle-Free Graphs.
Comb. Probab. Comput., 2012

Symmetric Determinantal Representations in Characteristic 2
CoRR, 2012

2011
Kernel bounds for disjoint cycles and disjoint paths.
Theor. Comput. Sci., 2011

The Domination Number of Grids.
SIAM J. Discret. Math., 2011

Kernels for feedback arc set in tournaments.
J. Comput. Syst. Sci., 2011

Realizing disjoint degree sequences of span at most two: A tractable discrete tomography problem.
Discret. Appl. Math., 2011

Conflict Packing yields linear vertex-kernels for Rooted Triplet Inconsistency and other problems
CoRR, 2011

Conflict Packing Yields Linear Vertex-Kernels for k -FAST, k -dense RTI and a Related Problem.
Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

2010
A 4<i>k</i><sup>2</sup> kernel for feedback vertex set.
ACM Trans. Algorithms, 2010

Well-Quasi-Order of Relabel Functions.
Order, 2010

Partitioning a graph into a cycle and an anticycle, a proof of Lehel's conjecture.
J. Comb. Theory, Ser. B, 2010

Partitions versus sets: A case of duality.
Eur. J. Comb., 2010

WDM and Directed Star Arboricity.
Comb. Probab. Comput., 2010

Edge Growth in Graph Cubes
CoRR, 2010

2009
Spanning galaxies in digraphs.
Electron. Notes Discret. Math., 2009

Submodular partition functions.
Discret. Math., 2009

Complexity of (p, 1)-total labelling.
Discret. Appl. Math., 2009

A Polynomial Kernel for Multicut in Trees.
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

A quadratic kernel for feedback vertex set.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

On Finding Directed Trees with Many Leaves.
Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

2008
Finding a vector orthogonal to roughly half a collection of vectors.
J. Complex., 2008

Hoàng-Reed conjecture holds for tournaments.
Discret. Math., 2008

Guarding Art Galleries: The Extra Cost for Sculptures Is Linear.
Proceedings of the Algorithm Theory, 2008

2007
Paths with two blocks in n-chromatic digraphs.
J. Comb. Theory, Ser. B, 2007

The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments.
Comb. Probab. Comput., 2007

Graphs with Large Girth Not Embeddable in the Sphere.
Comb. Probab. Comput., 2007

Total domination of graphs and small transversals of hypergraphs.
Comb., 2007

Spanning a strong digraph by <i>alpha</i> circuits: A proof of Gallai's conjecture.
Comb., 2007

2006
Density Conditions For Triangles In Multipartite Graphs.
Comb., 2006

2005
Preface.
Discret. Math., 2005

The categorical product of two 5-chromatic digraphs can be 3-chromatic.
Discret. Math., 2005

2004
The <i>C</i><sub>3</sub>-structure of the tournaments.
Discret. Math., 2004

Three Min-Max Theorems Concerning Cyclic Orders of Strong Digraphs.
Proceedings of the Integer Programming and Combinatorial Optimization, 2004

2003
Small degree out-branchings.
Journal of Graph Theory, 2003

Every strong digraph has a spanning strong subgraph with at most <i>n</i>+2 alpha-2 arcs.
J. Comb. Theory, Ser. B, 2003

Highly connected hypergraphs containing no two edge-disjoint spanning connected subhypergraphs.
Discret. Appl. Math., 2003

2002
Generalized Pigeonhole Properties of Graphs and Oriented Graphs<sup>*1</sup>.
Eur. J. Comb., 2002

2001
Covering a Strong Digraph by -1 Disjoint Paths: A Proof of Las Vergnas' Conjecture.
J. Comb. Theory, Ser. B, 2001

Countable alpha-extendable graphs.
Discret. Math., 2001

2000
Median orders of tournaments: A tool for the second neighborhood problem and Sumner's conjecture.
Journal of Graph Theory, 2000

Oriented Hamiltonian Paths in Tournaments: A Proof of Rosenfeld's Conjecture.
J. Comb. Theory, Ser. B, 2000

1998
2-Partition-Transitive Tournaments.
J. Comb. Theory, Ser. B, 1998

1997
Indivisibility and Alpha-morphisms.
Eur. J. Comb., 1997