Stéphan Thomassé

CoRR, 2024

Temporalizing Digraphs via Linear-Size Balanced Bi-Trees.

[BibT_eX]

[DOI]

Laurent Viennot

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

Factoring Pattern-Free Permutations into Separable ones.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Bounded twin-width graphs are polynomially χ-bounded.

[BibT_eX]

[DOI]

Romain Bourneuf

CoRR, 2023

Maximum Independent Set when excluding an induced minor: K1 + tK2 and tC3 ⊎ C4.

[BibT_eX]

[DOI]

CoRR, 2023

Extremal Independent Set Reconfiguration.

[BibT_eX]

[DOI]

Electron. J. Comb., 2023

Twin-Width V: Linear Minors, Modular Counting, and Matrix Multiplication.

[BibT_eX]

[DOI]

Édouard Bonnet

Ugo Giocanti

Patrice Ossona de Mendez

Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023

Sparse graphs with bounded induced cycle packing number have logarithmic treewidth.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

First Order Logic and Twin-Width in Tournaments.

[BibT_eX]

[DOI]

Colin Geniet

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

Lossy Kernelization for (Implicit) Hitting Set Problems.

[BibT_eX]

[DOI]

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

Maximum Independent Set When Excluding an Induced Minor: K₁ + tK₂ and tC₃ ⊎ C₄.

[BibT_eX]

[DOI]

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

Edge-partitioning 3-edge-connected graphs into paths.

[BibT_eX]

[DOI]

Tereza Klimosová

J. Comb. Theory, Ser. B, 2022

Degeneracy of Pt-free and C⩾t-free graphs with no large complete bipartite subgraphs.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, 2022

Graphs with polynomially many minimal separators.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, 2022

Twin-width I: Tractable FO Model Checking.

[BibT_eX]

[DOI]

J. ACM, 2022

A quasi-quadratic vertex Kernel for Cograph edge editing.

[BibT_eX]

[DOI]

Christophe Crespelle

Rémi Pellerin

CoRR, 2022

(P6, triangle)-free digraphs have bounded dichromatic number.

[BibT_eX]

[DOI]

CoRR, 2022

First Order Logic and Twin-Width in Tournaments and Dense Oriented Graphs.

[BibT_eX]

[DOI]

Colin Geniet

CoRR, 2022

Twin-width VII: groups.

[BibT_eX]

[DOI]

CoRR, 2022

Twin-width and Polynomial Kernels.

[BibT_eX]

[DOI]

Algorithmica, 2022

Twin-width IV: ordered graphs and matrices.

[BibT_eX]

[DOI]

Édouard Bonnet

Ugo Giocanti

Patrice Ossona de Mendez

Pierre Simon

Szymon Torunczyk

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Twin-width VI: the lens of contraction sequences.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Twin-Width VIII: Delineation and Win-Wins.

[BibT_eX]

[DOI]

Proceedings of the 17th International Symposium on Parameterized and Exact Computation, 2022

A Brief Tour in Twin-Width (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

(Theta, triangle)-free and (even hole, K4)-free graphs. Part 2: Bounds on treewidth.

[BibT_eX]

[DOI]

J. Graph Theory, 2021

Edge-decomposing graphs into coprime forests.

[BibT_eX]

[DOI]

Tereza Klimosová

J. Graph Theory, 2021

Disproving the normal graph conjecture.

[BibT_eX]

[DOI]

Ararat Harutyunyan

Lucas Pastor

J. Comb. Theory, Ser. B, 2021

EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs.

[BibT_eX]

[DOI]

J. ACM, 2021

Convexly independent subsets of Minkowski sums of convex polygons.

[BibT_eX]

[DOI]

Mateusz Skomra

Discret. Math., 2021

Twin-width and permutations.

[BibT_eX]

[DOI]

Édouard Bonnet

Jaroslav Nesetril

Patrice Ossona de Mendez

Sebastian Siebertz

CoRR, 2021

Twin-width II: small classes.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Twin-width III: Max Independent Set, Min Dominating Set, and Coloring.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2020

Twin-width III: Max Independent Set and Coloring.

[BibT_eX]

[DOI]

CoRR, 2020

Parameterized Complexity of Independent Set in H-Free Graphs.

[BibT_eX]

[DOI]

Algorithmica, 2020

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

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

An Algorithmic Weakening of the Erdős-Hajnal Conjecture.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

Testing Balanced Splitting Cycles in Complete Triangulations.

[BibT_eX]

Vincent Despré

Michaël Rao

Proceedings of the 32nd Canadian Conference on Computational Geometry, 2020

2019

Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2019

Coloring tournaments: From local to global.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, 2019

A proof of the Erdős-Sands-Sauer-Woodrow conjecture.

[BibT_eX]

[DOI]

William Lochet

J. Comb. Theory, Ser. B, 2019

Separation Choosability and Dense Bipartite Induced Subgraphs.

[BibT_eX]

[DOI]

Louis Esperet

Ross J. Kang

Comb. Probab. Comput., 2019

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

[BibT_eX]

[DOI]

CoRR, 2019

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

[BibT_eX]

[DOI]

CoRR, 2019

Subdivisions in Digraphs of Large Out-Degree or Large Dichromatic Number.

[BibT_eX]

[DOI]

Electron. J. Comb., 2019

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

[BibT_eX]

[DOI]

Comb., 2019

The Independent Set Problem Is FPT for Even-Hole-Free Graphs.

[BibT_eX]

[DOI]

Edin Husic

Proceedings of the 14th International Symposium on Parameterized and Exact Computation, 2019

When Maximum Stable Set Can Be Solved in FPT Time.

[BibT_eX]

[DOI]

Proceedings of the 30th International Symposium on Algorithms and Computation, 2019

2018

Multicut Is FPT.

[BibT_eX]

[DOI]

Jean Daligault

SIAM J. Comput., 2018

Domination in tournaments.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, 2018

Domination and Fractional Domination in Digraphs.

[BibT_eX]

[DOI]

Electron. J. Comb., 2018

Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

EPTAS for Max Clique on Disks and Unit Balls.

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

A proof of the Barát-Thomassen conjecture.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, 2017

Decomposing graphs into paths and trees.

[BibT_eX]

[DOI]

Tereza Klimosová

Rémi de Joannis de Verclos

Electron. Notes Discret. Math., 2017

Coloring dense digraphs.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2017

Additive bases and flows in graphs.

[BibT_eX]

[DOI]

Louis Esperet

Tien-Nam Le

Electron. Notes Discret. Math., 2017

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

[BibT_eX]

[DOI]

Kristina Vuskovic

Algorithmica, 2017

On the Complexity of Partial Derivatives.

[BibT_eX]

[DOI]

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

2016

Isolating Highly Connected Induced Subgraphs.

[BibT_eX]

[DOI]

Irena Penev

SIAM J. Discret. Math., 2016

The Erdös-Hajnal Conjecture for Long Holes and Antiholes.

[BibT_eX]

[DOI]

Marthe Bonamy

SIAM J. Discret. Math., 2016

Perfect graphs of arbitrarily large clique-chromatic number.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, 2016

Linear kernel for Rooted Triplet Inconsistency and other problems based on conflict packing technique.

[BibT_eX]

[DOI]

Christophe Paul

Anthony Perez

J. Comput. Syst. Sci., 2016

2015

Identifying Codes in Hereditary Classes of Graphs and VC-Dimension.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2015

The Erdős-Hajnal conjecture for paths and antipaths.

[BibT_eX]

[DOI]

Aurélie Lagoutte

J. Comb. Theory, Ser. B, 2015

A $$\tau $$ τ -Conjecture for Newton Polygons.

[BibT_eX]

[DOI]

Found. Comput. Math., 2015

Excluding clocks.

[BibT_eX]

[DOI]

Pierre Aboulker

Zhentao Li

Electron. Notes Discret. Math., 2015

VC-dimension and Erdős-Pósa property.

[BibT_eX]

[DOI]

Discret. Math., 2015

2014

Hitting and Harvesting Pumpkins.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2014

Parameterized Domination in Circle Graphs.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2014

Disjoint 3-Cycles in Tournaments: A Proof of The Bermond-Thomassen Conjecture for Tournaments.

[BibT_eX]

[DOI]

Jørgen Bang-Jensen

J. Graph Theory, 2014

Satisfying more than half of a system of linear equations over GF(2): A multivariate approach.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2014

Clique versus independent set.

[BibT_eX]

[DOI]

Aurélie Lagoutte

Eur. J. Comb., 2014

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

[BibT_eX]

[DOI]

Marthe Bonamy

CoRR, 2014

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

[BibT_eX]

[DOI]

Marthe Bonamy

CoRR, 2014

A Note on the Minimum Distance of Quantum LDPC Codes.

[BibT_eX]

[DOI]

Nicolas Delfosse

Zhentao Li

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

2013

A counterexample to a conjecture of Schwartz.

[BibT_eX]

[DOI]

Soc. Choice Welf., 2013

Tournaments and colouring.

[BibT_eX]

[DOI]

Eli Berger

Krzysztof Choromanski

J. Comb. Theory, Ser. B, 2013

A linear vertex kernel for maximum internal spanning tree.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2013

Oriented trees in digraphs.

[BibT_eX]

[DOI]

Louigi Addario-Berry

Cláudia Linhares Sales

Bruce A. Reed

Discret. Math., 2013

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

[BibT_eX]

[DOI]

Kristina Vuskovic

CoRR, 2013

A tau-conjecture for Newton polygons.

[BibT_eX]

[DOI]

CoRR, 2013

Graph coloring, communication complexity and the stubborn problem (Invited talk).

[BibT_eX]

[DOI]

Aurélie Lagoutte

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

2012

Cyclic orderings and cyclic arboricity of matroids.

[BibT_eX]

[DOI]

Jan van den Heuvel

J. Comb. Theory, Ser. B, 2012

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

[BibT_eX]

[DOI]

Penny E. Haxell

Alexandr V. Kostochka

Graphs Comb., 2012

A stability theorem on fractional covering of triangles by edges.

[BibT_eX]

[DOI]

Penny E. Haxell

Alexandr V. Kostochka

Eur. J. Comb., 2012

Scott's Induced Subdivision Conjecture for Maximal Triangle-Free Graphs.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2012

Symmetric Determinantal Representations in Characteristic 2

[BibT_eX]

[DOI]

Bruno Grenet

Thierry Monteil

CoRR, 2012

2011

Kernel bounds for disjoint cycles and disjoint paths.

[BibT_eX]

[DOI]

Hans L. Bodlaender

Theor. Comput. Sci., 2011

The Domination Number of Grids.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2011

Kernels for feedback arc set in tournaments.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2011

Realizing disjoint degree sequences of span at most two: A tractable discrete tomography problem.

[BibT_eX]

[DOI]

Flavio Guiñez

Martín Matamala

Discret. Appl. Math., 2011

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

[BibT_eX]

[DOI]

Christophe Paul

Anthony Perez

CoRR, 2011

Conflict Packing Yields Linear Vertex-Kernels for k -FAST, k -dense RTI and a Related Problem.

[BibT_eX]

[DOI]

Christophe Paul

Anthony Perez

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.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

2010

A 4k2 kernel for feedback vertex set.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2010

Well-Quasi-Order of Relabel Functions.

[BibT_eX]

[DOI]

Jean Daligault

Michaël Rao

Order, 2010

Partitioning a graph into a cycle and an anticycle, a proof of Lehel's conjecture.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, 2010

Partitions versus sets: A case of duality.

[BibT_eX]

[DOI]

Laurent Lyaudet

Frédéric Mazoit

Eur. J. Comb., 2010

WDM and Directed Star Arboricity.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2010

Edge Growth in Graph Cubes

[BibT_eX]

[DOI]

Matt DeVos

CoRR, 2010

2009

Spanning galaxies in digraphs.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2009

Submodular partition functions.

[BibT_eX]

[DOI]

Discret. Math., 2009

Complexity of (p, 1)-total labelling.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2009

A Polynomial Kernel for Multicut in Trees.

[BibT_eX]

[DOI]

Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

A quadratic kernel for feedback vertex set.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

On Finding Directed Trees with Many Leaves.

[BibT_eX]

[DOI]

Jean Daligault

Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

2008

Finding a vector orthogonal to roughly half a collection of vectors.

[BibT_eX]

[DOI]

J. Complex., 2008

Hoàng-Reed conjecture holds for tournaments.

[BibT_eX]

[DOI]

Discret. Math., 2008

Guarding Art Galleries: The Extra Cost for Sculptures Is Linear.

[BibT_eX]

[DOI]

Louigi Addario-Berry

Omid Amini

Jean-Sébastien Sereni

Proceedings of the Algorithm Theory, 2008

2007

Paths with two blocks in n-chromatic digraphs.

[BibT_eX]

[DOI]

Louigi Addario-Berry

J. Comb. Theory, Ser. B, 2007

The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2007

Graphs with Large Girth Not Embeddable in the Sphere.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2007

Total domination of graphs and small transversals of hypergraphs.

[BibT_eX]

[DOI]

Comb., 2007

Spanning a strong digraph by alpha circuits: A proof of Gallai's conjecture.

[BibT_eX]

[DOI]

Comb., 2007

2006

Density Conditions For Triangles In Multipartite Graphs.

[BibT_eX]

[DOI]

Comb., 2006

2005

Preface.

[BibT_eX]

[DOI]

Gena Hahn

Pierre Ille

Discret. Math., 2005

The categorical product of two 5-chromatic digraphs can be 3-chromatic.

[BibT_eX]

[DOI]

Discret. Math., 2005

2004

The C3-structure of the tournaments.

[BibT_eX]

[DOI]

Discret. Math., 2004

Three Min-Max Theorems Concerning Cyclic Orders of Strong Digraphs.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2004

2003

Small degree out-branchings.

[BibT_eX]

[DOI]

Jørgen Bang-Jensen

J. Graph Theory, 2003

Every strong digraph has a spanning strong subgraph with at most n+2 alpha-2 arcs.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, 2003

Highly connected hypergraphs containing no two edge-disjoint spanning connected subhypergraphs.

[BibT_eX]

[DOI]

Jørgen Bang-Jensen

Discret. Appl. Math., 2003

2002

Generalized Pigeonhole Properties of Graphs and Oriented Graphs*1.

[BibT_eX]

[DOI]

Eur. J. Comb., 2002

2001

Covering a Strong Digraph by -1 Disjoint Paths: A Proof of Las Vergnas' Conjecture.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, 2001

Countable alpha-extendable graphs.

[BibT_eX]

[DOI]

Jean-Luc Rullière

Discret. Math., 2001

2000

Median orders of tournaments: A tool for the second neighborhood problem and Sumner's conjecture.

[BibT_eX]

[DOI]

J. Graph Theory, 2000

Oriented Hamiltonian Paths in Tournaments: A Proof of Rosenfeld's Conjecture.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, 2000

1998

2-Partition-Transitive Tournaments.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, 1998

1997

Indivisibility and Alpha-morphisms.

[BibT_eX]

[DOI]