Stéphan Thomassé

Professeur au département d'informatique de l'Ecole Normale Supérieure de Lyon
Laboratoire / Laboratory : Laboratoire de l'informatique du parallélisme (LIP)
Equipe / Research Team : Modèles de calcul, Complexité, Combinatoire (MC2)
Membre de l'Institut Universitaire de France 2016-2021

Contact & Vita :

LIP, ENS Lyon, 46 allée d'Italie, 69364 Lyon Cedex 07 - France.
Tél. : 04 72 72 86 83 (de France) +33 472 728 683 (from abroad)
Bureau / Office : 316 GN1 SUD
Mail : firstname.name (no accents) at ens-lyon.fr
(very old) Curriculum vitae : In french . En anglais.

Enseignement / Teaching :

Décompositions Arborescentes et Algorithmes FPT. M2 Informatique Fondamentale (2011-2013).

Graphs and Polynomials. M2 Informatique Fondamentale (2013-2015).

Probabilistic methods, with Applications to Graphs. M2 Systèmes Complexes (2014-2016).

Optimization and Approximation. M1 Informatique Fondamentale (2013-2016).

Fondements de l'Informatique. L3 Informatique Fondamentale (2015-2016).

Introduction à l'Informatique. M2 Systèmes Complexes (2015-2016).

Information Theory. M1 Informatique Fondamentale (2017-2018).

Computer Algebra. M1 Informatique Fondamentale (2018-2019).

Lower bound methods. M2 Informatique Fondamentale (2017-2019).

Graph Decompositions. M2 Informatique Fondamentale (2021-2023).

Some course notes here

Responsabilités Collectives / Admin / Contracts:

Responsable du M2 Informatique Fondamentale (2013-2015).
Directeur adjoint du département d'informatique. (2013-2015)
Chef d'équipe MC2. (2015-2017, 2023-...)
Ancien membre des ANR GRAAL, AGAPE, STINT, COMPA.
Membre de l'ANR Digraphs.
Membre de l'ANR TWIN-WIDTH.

Conférences / Workshops :

Une liste de ceux auxquels j'ai participé.

Séminaires / Seminars :

Journées structures discrètes 1 et 2 du LIP.
Graphes@Lyon Groupe de travail Graphes et Structures discrètes.
GRAA Séminaire virtuel de théorie des graphes et combinatoire en Rhône-Alpes et Auvergne.
G-Scop Seminar Le Séminaire de Mathématiques Discrètes de Grenoble.
GT Graphes et Optimisation Le Séminaire de Graphes de Bordeaux.
Combinatorics lectures online Link to many talks.

Preprints and Drafts :

A tamed family of triangle-free graphs with unbounded chromatic number. With É. Bonnet, R. Bourneuf, J. Duron, C. Geniet and N. Trotignon.
Bounded twin-width graphs are polynomially chi-bounded. With R. Bourneuf.
Twin-width VII: groups. With É. Bonnet, C. Geniet and R. Tessera.
Graphs with large chromatic number induce 3k-cycles. With M. Bonamy and P. Charbit.
Edge growth in graph cubes. With M. DeVos.
Coloring dense graphs via VC-dimension. With T. Łuczak.
Dense triangle-free graphs are four colorable: A solution to the Erdős-Simonovits problem. With S. Brandt.

Computer Science Conferences :

Vertex-minor universal graphs for generating entangled quantum subsystems. With M. Cautrès, N. Claudet, M. Mhalla, S. Perdrix and V. Savin, ICALP 2024.
Temporalizing digraphs via linear-size balanced bi-trees. With S. Bessy and L. Viennot, STACS 2024.
Factoring Pattern-Free Permutations into Separable ones. With É. Bonnet, R. Bourneuf and C. Geniet, SODA 2024.
Maximum Independent Set When Excluding an Induced Minor: K1 + tK2 and tC3 U C4. With É. Bonnet, J. Duron, C. Geniet and A. Wesolek, ESA 2023.
Lossy Kernelization for (Implicit) Hitting Set Problems. With F. Fomin, T.N. Le, D. Lokshtanov, S. Saurabh and M. Zehavi, ESA 2023.
First Order Logic and Twin-Width in Tournaments. With C. Geniet, ESA 2023.
Twin-width V: linear minors, modular counting, and matrix multiplication. With É. Bonnet, U. Giocanti and P. Ossona de Mendez, STACS 2023.
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth. With M. Bonamy, É. Bonnet, H. Déprés, L. Esperet, C. Geniet, C. Hilaire and A. Wesolek, SODA 2023.
Twin-width VIII: delineation and win-wins. With É. Bonnet, D. Chakraborty, E.J. Kim, N. Köhler and R. Lopes, IPEC 2022.
Twin-width IV: ordered graphs and matrices. With É. Bonnet, U. Giocanti, P. Ossona de Mendez, P. Simon and S. Toruńczyk, STOC 2022.
Twin-width VI: the lens of contraction sequences. With É. Bonnet, E.J. Kim and A. Reinald, SODA 2022.
Twin-width and polynomial kernels. With É. Bonnet, E.J. Kim, A. Reinald and R. Watrigant, IPEC 2021.
Twin-width III: Max Independent Set, Min Dominating Set and Coloring. With É. Bonnet, C. Geniet, E.J. Kim and R. Watrigant, ICALP 2021.
Twin-width II: small classes. With É. Bonnet, C. Geniet, E.J. Kim and R. Watrigant, SODA 2021.
Testing Balanced Splitting Cycles in Complete Triangulations. With V. Despré and M. Rao, CCCG 2020.
Twin-width I: tractable FO model checking. With É. Bonnet, E.J. Kim and R. Watrigant, FOCS 2020.
An Algorithmic Weakening of the Erdős-Hajnal Conjecture. With É. Bonnet, X.T. Tran and R. Watrigant, ESA 2020.
Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs. With M. Chudnovsky, M. Pilipczuk and M. Pilipczuk, SODA 2020.
When Maximum Stable Set Can Be Solved in FPT Time. With É. Bonnet, N. Bousquet and R. Watrigant, ISAAC 2019.
The independent set problem is FPT for even-hole-free graphs. With E. Husić and N. Trotignon, IPEC 2019.
EPTAS for Max Clique on Disks and Unit Balls. With M. Bonamy, É. Bonnet, N. Bousquet and P. Charbit, FOCS 2018.
Parameterized Complexity of Independent Set in H-Free Graphs. With É. Bonnet, N. Bousquet, P. Charbit and R. Watrigant, IPEC 2018.
Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems. With T.N. Le, D. Lokshtanov, S. Saurabh and M. Zehavi, SODA 2018.
On the complexity of partial derivatives. With I. Garcia-Marco, P. Koiran and T. Pecatte, STACS 2017.
A note on the minimum distance of quantum LDPC codes. With N. Delfosse and Z. Li, MFCS 2014.
Parameterized algorithm for weighted independent set problem in bull-free graphs. With N. Trotignon and K. Vušković, WG 2014.
Parameterized domination in circle graphs. With N. Bousquet, D. Gonçalves, G. Mertzios, C. Paul and I. Sau, WG 2012.
Linear vertex-kernels through conflict packing: Application to FAST and RTI problems. With C. Paul and A. Perez, MFCS 2011.
Multicut is FPT. With N. Bousquet and J. Daligault, STOC 2011.
Hitting and harvesting pumpkins. With G. Joret, C. Paul, I. Sau and S. Saurabh, ESA 2011.
Simultaneously satisfying linear equations over F2. With R. Crowston, M. Fellows, G. Gutin, M. Jones, E.J. Kim, F. Rosamond, I.Z. Ruzsa and A. Yeo, FSTTCS 2011.
Kernel bounds for disjoint cycles and disjoint paths. With H. Bodlaender and A. Yeo, ESA 2009.
A quadratic kernel for feedback vertex set, SODA 2009.
Kernels for Feedback Arc Set in Tournaments. With S. Bessy, F. Fomin, S. Gaspers, C. Paul, A. Perez and S. Saurabh, FSTTCS 2009.
A 3k kernel for Maximum Internal Spanning Tree. With F. Fomin, S. Gaspers and S. Saurabh, ISAAC 2009.
On finding directed trees with many leaves. With J. Daligault, IWPEC 2009.
A polynomial kernel for Multicut In Trees. With N. Bousquet, J. Daligault and A. Yeo, STACS 2009.
Guarding art galleries: The extra cost for sculptures is linear. With L. Addario-Berry, O. Amini and J.S. Sereni, SWAT 2008.
Three min-max theorems concerning cyclic orders of strong digraphs. With S. Bessy, IPCO 2004.

Journals :

A quasi-quadratic vertex-kernel for Cograph Edge Editing. With C. Crespelle and R. Pellerin, Discrete Applied Mathematics, 357 (2024), 282-296.
Clique covers of H-free graphs. With T. Nguyen, A. Scott and P. Seymour, European J. Combin., 118 (2024), 103909.
Twin-width IV: ordered graphs and matrices. With É. Bonnet, U. Giocanti, P. Ossona de Mendez, P. Simon and S. Toruńczyk, J. ACM, 71 (2024), 3:21.
Twin-width III: Max Independent Set, Min Dominating Set and Coloring. With É. Bonnet, C. Geniet, E.J. Kim and R. Watrigant, SIAM J. Comput., 53 (2024), 1602-1640.
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth. With M. Bonamy, É. Bonnet, H. Déprés, L. Esperet, C. Geniet, C. Hilaire and A. Wesolek, J. Combin. Theory Ser. B, 167 (2024), 215-249.
Twin-width and permutations. With É. Bonnet, J. Nešetřil, P. Ossona de Mendez and S. Siebertz, Log. Methods Comput. Sci., 20 (2024), 3.
Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs. With M. Chudnovsky, M. Pilipczuk and M. Pilipczuk, SIAM J. Comput., 53 (2024), 47-86.
Extremal Independent Set Reconfiguration. With N. Bousquet, B. Durain and T. Pierron, Electr. J. Comb., 30 (2023), P3.8.
Twin-width and polynomial kernels. With É. Bonnet, E.J. Kim, A. Reinald and R. Watrigant, Algorithmica, 84 (2022), 3300-3337.
Edge-partitioning 3-edge-connected graphs into paths. With T. Klimošová, J. Combin. Theory Ser. B, 156 (2022), 250-293.
Twin-width II: small classes. With É. Bonnet, C. Geniet, E.J. Kim and R. Watrigant, Combinatorial Theory, 2 (2022).
Twin-width I: Tractable FO model checking. With É. Bonnet, E.J. Kim and R. Watrigant, J. ACM, 69 (2022), 3:1-46.
Graphs with polynomially many minimal separators. With T. Abrishami, M. Chudnovsky, C. Dibek, N. Trotignon and K. Vušković, J. Combin. Theory Ser. B, 152 (2022), 248-280.
Degeneracy of Pt-free and C≥t-free graphs with no large complete bipartite subgraphs. With M. Bonamy, N. Bousquet, M. Pilipczuk, P. Rzążewski and B. Walczak, J. Combin. Theory Ser. B, 152 (2022), 353-378.
Convexly independent subsets of Minkowski sums of convex polygons. With M. Skomra, Discrete Mathematics, 344 (2021), 112472.
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs. With M. Bonamy, É. Bonnet, N. Bousquet, P. Charbit, P. Giannopoulos, E.J. Kim, P. Rzążewski and F. Sikora, J. ACM, 68 (2021), 9:1-38.
Disproving the normal graph conjecture. With A. Harutyunyan and L. Pastor, J. Combin. Theory Ser. B, 147 (2021), 238-251.
Edge-decomposing graphs into coprime forests. With T. Klimošová, J. Graph Theory, 97 (2021), 21-33.
(Theta, triangle)-free and (even hole, K₄)-free graphs. Part 2: Bounds on treewidth. With M. Pilipczuk, N.L.D. Sintiari and N. Trotignon J. Graph Theory, 97 (2021), 624-641.
On the Maximum Weight Independent Set Problem in graphs without induced cycles of length at least five. With M. Chudnovsky, M. Pilipczuk and M. Pilipczuk, SIAM J. Discrete Math., 34 (2020), 1472-1483.
Parameterized Complexity of Independent Set in H-Free Graphs. With É. Bonnet, N. Bousquet, P. Charbit and R. Watrigant, Algorithmica, 82 (2020), 2360-2394.
Separation choosability and dense bipartite induced subgraphs. With L. Esperet and R.J. Kang, Combinatorics, Probability and Computing, 28 (2019), 720-732.
Subdivisions in digraphs of large out-degree or large dichromatic number. With P. Aboulker, N. Cohen, F. Havet, W. Lochet and P.F.S. Moura, Electr. J. Comb., 26 (2019), P3.19.
Coloring tournaments: from local to global. With A. Harutyunyan, T.N. Le and H. Wu, J. Combin. Theory Ser. B, 138 (2019), 166-171.
A proof of the Erdős-Sands-Sauer-Woodrow conjecture. With N. Bousquet and W. Lochet, J. Combin. Theory Ser. B, 137 (2019), 316-319.
Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture. With J. Bensmail, A. Harutyunyan and T.N. Le, Combinatorica, 39 (2019), 239-263.
Realization of aperiodic subshifts and densities in groups. With N. Aubrun and S. Barbieri, Groups, Geometry and Dynamics, 13 (2019), 107-129.
Coloring dense digraphs. With A. Harutyunyan, T.N. Le and A. Newman, Combinatorica, 39 (2019), 1021-1053.
Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems. With T.N. Le, D. Lokshtanov, S. Saurabh and M. Zehavi, ACM Transactions on Algorithms, 15 (2019), Art. 13, 44 pp.
Domination and fractional domination in digraphs. With A. Harutyunyan, T.N. Le and A. Newman, Electr. J. Comb., 25 (2018), P3.32.
Domination in tournaments. With M. Chudnovsky, R. Kim, C.-H. Liu and P. Seymour, J. Combin. Theory Ser. B, 130 (2018), 98-113.
Additive bases and flows in graphs. With L. Esperet, R. de Joannis de Verclos and T.N. Le, SIAM J. Discrete Math., 32 (2018), 534-542.
Multicut is FPT. With N. Bousquet and J. Daligault, SIAM J. Comput., 47 (2018), 166-207.
A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs. With N. Trotignon and K. Vušković, Algorithmica, 77 (2017), 619-641.
A proof of the Barát-Thomassen conjecture. With J. Bensmail, A. Harutyunyan, T.N. Le and M. Merker, J. Combin. Theory Ser. B, 124 (2017), 39-55.
The Erdős-Hajnal conjecture for long holes and antiholes. With M. Bonamy and N. Bousquet, SIAM J. Discrete Math., 30 (2016), 1159-1164.
Perfect graphs of arbitrarily large clique-chromatic number. With P. Charbit, I. Penev and N. Trotignon, J. Combin. Theory Ser. B, 116 (2016), 456-464.
Isolating highly connected induced subgraphs. With I. Penev and N. Trotignon, SIAM J. Discrete Math., 30 (2016), 592-619.
Linear kernel for Rooted Triplet Inconsistency and other problems based on conflict packing technique. With C. Paul and A. Perez, J. Comput. Syst. Sci., 82 (2016), 366-379.
VC-dimension and Erdős-Pósa property. With N. Bousquet, Discrete Mathematics, 338 (2015), 2302-2317.
Identifying codes in hereditary classes of graphs and VC-dimension. With N. Bousquet, A. Lagoutte, Z. Li and A. Parreau, SIAM J. of Discrete Maths, 29 (2015), 2047-2064.
The Erdős-Hajnal conjecture for paths and antipaths. With N. Bousquet and A. Lagoutte, J. Combin. Theory Ser. B, 113 (2015), 261-264.
A tau-conjecture for Newton polygons. With P. Koiran, N. Portier and S. Tavenas, Foundations of Computational Mathematics, 15 (2015), 185-197.
Clique versus independent set. With N. Bousquet and A. Lagoutte, European J. Combin., 40 (2014), 73-92.
Disjoint circuits in tournaments, beyond the Bermond-Thomassen conjecture. With J. Bang-Jensen and S. Bessy, J. Graph Theory, 75 (2014), 284-302.
Parameterized domination in circle graphs. With N. Bousquet, D. Gonçalves, G. Mertzios, C. Paul and I. Sau, Theory Comput. Syst., 54 (2014), 45-72.
Hitting and harvesting pumpkins. With G. Joret, C. Paul, I. Sau and S. Saurabh, SIAM J. Discrete Math., 28 (2014), 1363-1390.
Satisfying more than half of a system of linear equationsover GF(2): A multivariate approach. With R. Crowston, M. Fellows, G. Gutin, M. Jones, E.J. Kim, F. Rosamond, I. Z. Ruzsa and A. Yeo, J. Comput. Syst. Sci., 80 (2014), 687-696.
Complements of nearly perfect graphs. With A. Gyárfás, Z. Li, R. Machado, A. Sebő and N. Trotignon, Journal of Combinatorics, 4 (2013), 299-310.
A counterexample to a conjecture of Schwartz. With F. Brandt, M. Chudnovsky, I. Kim, G. Liu, S. Norin, A. Scott and P. Seymour, Social Choice and Welfare, 40 (2013), 739-743.
Symmetric determinantal representations in characteristic 2. With B. Grenet and T. Monteil, Linear Algebra and its Applications, 439 (2013), 1364-1381.
Oriented trees in digraphs. With L. Addario-Berry, F. Havet, C. Linhares Sales and B. Reed, Discrete Mathematics, 313 (2013), 967-974.
A linear vertex kernel for maximum internal spanning tree. With F. Fomin, S. Gaspers and S. Saurabh, J. Comput. Syst. Sci., 79 (2013), 1-6.
Tournaments and colouring. With E. Berger, K. Choromanski, M. Chudnovsky, J. Fox, M. Loebl, A. Scott and P. Seymour, J. Combin. Theory Ser. B, 103 (2013), 1-20.
A stability theorem on fractional covering of triangles by edges. With P. Haxell and A. Kostochka, European J. Combin., 33 (2012), 799-806.
Cyclic orderings and cyclic arboricity of matroids. With J. van den Heuvel, J. Combin. Theory Ser. B, 102 (2012), 638-646.
Scott's induced subdivision conjecture for maximal triangle-free graphs. With N. Bousquet, Combinatorics, Probability and Computing, 21 (2012), 512-514.
Packing and covering triangles in K4-free planar graphs. With P. Haxell and A. Kostochka, Graphs and Combinatorics, 28 (2012), 653-662.
On spanning galaxies in digraphs. With D. Gonçalves, F. Havet and A. Pinlou, Discrete Applied Mathematics, 160 (2012), 744-754.
The Domination Number of Grids. With D. Gonçalves, A. Pinlou and M. Rao, SIAM J. of Discrete Maths, 25 (2011), 1443-1453.
Realizing disjoint degree sequences of span at most two: A tractable discrete tomography problem. With F. Guíñez and M. Matamala, Discrete Applied Mathematics, 159 (2011), 23-30.
Kernels for Feedback Arc Set in Tournaments. With S. Bessy, F. Fomin, S. Gaspers, C. Paul, A. Perez and S. Saurabh, J. Comput. Syst. Sci., 77 (2011), 1071-1078.
Kernel bounds for disjoint cycles and disjoint paths. With H. Bodlaender and A. Yeo, Theoretical Computer Science, 412 (2011), 4570-4578.
Partitions versus sets: A case of duality. With L. Lyaudet and F. Mazoit, European J. Combin., 31 (2010), 681-687.
Partitioning a graph into a cycle and an anticycle: a proof of Lehel's conjecture. With S. Bessy, J. Combin. Theory Ser. B, 100 (2010), 176-180.
WDM and directed star arboricity. With O. Amini, F. Havet and F. Huc, Combinatorics, Probability and Computing, 19 (2010), 161-182.
Well-quasi-order of relabel functions. With J. Daligault and M. Rao, Order, 27 (2010), 301-315.
A 4k² kernel for feedback vertex set. ACM Transactions on Algorithms, 6 (2010), Art. 32, 8 pp.
Submodular partition functions. With O. Amini, F. Mazoit and N. Nisse, Discrete Mathematics, 309 (2009), 6000-6008.
Complexity of (p,1)-total labelling. With F. Havet, Discrete Applied Mathematics, 157 (2009), 2859-2870.
Hoàng-Reed conjecture holds for tournaments. With F. Havet and A. Yeo, Discrete Mathematics, 308 (2008), 3412-3415.
Finding a vector orthogonal to roughly half a collection of vectors. With P. Charbit, E. Jeandel, P. Koiran and S. Perifel, J. of Complexity, 24 (2008), 39-53.
Paths with two blocks in n-chromatic digraphs. With L. Addario-Berry and F. Havet, J. Combin. Theory Ser. B, 97 (2007), 620-626.
Graphs with large girth not embeddable in the sphere. With P. Charbit, Combinatorics, Probability and Computing, 16 (2007), 829-832.
The minimum feedback arc set problem is NP-hard for tournament. With P. Charbit and A. Yeo, Combinatorics, Probability and Computing, 16 (2007), 1-4.
Spanning a strong digraph by α circuits: A proof of Gallai's conjecture. With S. Bessy, Combinatorica, 27 (2007), 659-667.
Partitions and orientations of the Rado graph. With R. Diestel, I. Leader and A. Scott, Trans. Amer. Math. Soc., 359 (2007), 2395-2405.
Total domination of graphs and small transversals of hypergraphs. With A. Yeo, Combinatorica, 27 (2007), 473-487.
Density conditions for triangles in multipartite graphs. With A. Bondy, J. Shen and C. Thomassen, Combinatorica, 26 (2006), 121-131.
The Categorical Product of two 5-chromatic digraphs can be 3-chromatic. With S. Bessy, Discrete Mathematics, 305 (2005), 344-346.
The C3-structure of tournaments. With A. Boussairi, P. Ille and G. Lopez, Discrete Mathematics, 277 (2004), 29-43.
Small degree out-branchings. With J. Bang-Jensen and A. Yeo, J. Graph Theory, 42 (2003), 297-307.
Highly connected hypergraphs containing no two edge-disjoint spanning connected subhypergraphs. With J. Bang-Jensen, Discrete Applied Mathematics, 131 (2003), 555-559.
Every strong digraph has a spanning strong subgraph with at most n+2α-2 arcs. With S. Bessy, J. Combin. Theory Ser. B, 87 (2003), 289-299.
Generalized pigeonhole properties of graphs and oriented graphs. With A. Bonato, P.J. Cameron and D. Delic, European J. Combin., 23 (2002), 257-274.
Covering a strong digraph by α-1 disjoint paths: a proof of Las Vergnas' conjecture, J. Combin. Theory Ser. B, 83 (2001), 331-333.
Countable α-extendable graphs. With J.L. Rullière, Discrete Mathematics, 239 (2001), 53-67.
Median orders of tournaments: a tool for the second neighborhood problem and Sumner's conjecture. With F. Havet, J. Graph Theory, 35 (2000), 244-256.
Oriented Hamiltonian paths in tournaments: a proof of Rosenfeld's conjecture. With F. Havet, J. Combin. Theory Ser. B, 78 (2000), 243-273.
On better-quasi-ordering countable series-parallel orders, Trans. Amer. Math. Soc., 352 (2000), 2491-2505.
2-partition-transitive tournaments. With B. Guiduli, A. Gyárfás and P. Weidl, J. Combin. Theory Ser. B, 72 (1998), 181-196.
Indivisibility and α-morphisms, European J. Combin., 18 (1997), 445-454.

Book Chapters and Notes :

Twin-width and permutations. With É. Bonnet, J. Nešetřil, P. Ossona de Mendez and S. Siebertz, EUROCOMB'23, 156-162.
Coloring dense digraphs. With A. Harutyunyan, T.N. Le and A. Newman, EUROCOMB'17, Electron. Notes Discret. Math., 61 (2017), 577-583.
Additive bases and flows in graphs. With L. Esperet, R. de Joannis de Verclos and T.N. Le, EUROCOMB'17, Electron. Notes Discret. Math., 61 (2017), 399-405.
Decomposing graphs into paths and trees. With T. Klimošová, EUROCOMB'17, Electron. Notes Discret. Math., 61 (2017), 751-757.
Excluding clocks. With P. Aboulker and Z. Li, LAGOS'15, Electron. Notes Discret. Math., 50 (2015), 103-108.
Almost all H-free graphs have the Erdős-Hajnal property. With M. Loebl, B. Reed, A. Scott and A. Thomason, An Irregular Mind, Szemerédi is 70, Bolyai Society Math. Studies, 21 (2010), 405-414.
Spanning galaxies in digraphs. With D. Gonçalves, F. Havet and A. Pinlou, EUROCOMB'09, Electron. Notes Discret. Math., 34 (2009), 139-143.
Guarding art galleries: The extra cost for sculptures is linear. With L. Addario-Berry, O. Amini and J.S. Sereni, LNCS, 5124 (2008), 41-52.
Branchwidth of graphic matroids. With F. Mazoit, Surveys in combinatorics 2007, London Math. Soc. Lecture Note Ser., 346 (2007), 275-286.
Convex cones and SAGBI bases of permutation invariants. With N. Thiéry, Invariant theory in all characteristics, CRM Proc. Lecture Notes, 35 (2004), 259-263.
Three min-max theorems concerning cyclic orders of strong digraphs.. With S. Bessy, LNCS, 3064 (2004), 132-138.
Relations infinies indécomposables critiques. With L. Rigollet, C. R. Acad. Sci. Paris Sér. I, 324 (1997), 249-252.
Hypomorphie et inversion locale entre graphes. With A. Boussairi, P. Ille and G. Lopez, C. R. Acad. Sci. Paris Sér. I, 317 (1993), 125-128.
Belordre des série-parallèles dénombrables. C. R. Acad. Sci. Paris Sér. I, 317 (1993), 909-912.