Stéphan Thomassé

  • Contact & Vita :
  • Enseignement / Teaching :
  • Responsabilités Collectives / Admin / Contracts:
  • Conférences / Workshops :

  • Séminaires / Seminars :

  • Publications : Mainly in Algorithms, Graphs, Discrete Geometry, and Combinatorial Optimization.
    1. Edge-partitioning 3-edge-connected graphs into paths. With T. Klimošová, submitted.
    2. Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs. With M. Chudnovsky, M. Pilipczuk and M. Pilipczuk, submitted.
    3. Convexly independent subsets of Minkowski sums of convex polygons. With M. Skomra, submitted.
    4. 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, submitted.
    5. Edge-decomposing graphs into coprime forests. With T. Klimošová, submitted.
    6. Disproving the normal graph conjecture. With A. Harutyunyan and L. Pastor, to appear.
    7. Graphs with large chromatic number induce 3k-cycles. With M. Bonamy and P. Charbit, to appear.
    8. Edge growth in graph cubes. With M. DeVos, submitted.
    9. Coloring dense graphs via VC-dimension. With T. Łuczak, submitted.
    10. Dense triangle-free graphs are four colorable: A solution to the Erdős-Simonovits problem. With S. Brandt, to appear.
    11. The independent set problem is FPT for even-hole-free graphs. With E. Husić and N. Trotignon, IPEC 2019.
    12. Separation choosability and dense bipartite induced subgraphs. With L. Esperet and R.J. Kang, Combinatorics, Probability and Computing, 28 (2019), 720-732.
    13. 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.
    14. Coloring tournaments: from local to global. With A. Harutyunyan, T.-N. Le and H. Wu, J. Combin. Theory Ser. B, 138 (2019), 166-171.
    15. 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.
    16. 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.
    17. Realization of aperiodic subshifts and densities in groups. With N. Aubrun and S. Barbieri, Groups, Geometry and Dynamics, 13 (2019), 107-129.
    18. EPTAS for Max Clique on Disks and Unit Balls. With M. Bonamy, É. Bonnet, N. Bousquet and P. Charbit, FOCS 2018.
    19. Parameterized Complexity of Independent Set in H-Free Graphs. With É. Bonnet, N. Bousquet, P. Charbit and R. Watrigant, IPEC 2018.
    20. Domination and fractional domination in digraphs. With A. Harutyunyan, T.-N. Le and A. Newman, Electr. J. Comb., 25 (2018), P3.32.
    21. Domination in tournaments. With M. Chudnovsky, R. Kim, C.-H. Liu and P. Seymour, J. Combin. Theory Ser. B, 130 (2018), 98-113.
    22. 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.
    23. 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, 331-342, ACM Transactions on Algorithms, 15 (2019), Art. 13, 44 pp.
    24. Coloring dense digraphs. With A. Harutyunyan, T.-N. Le and A. Newman, Electronic Notes in Discrete Mathematics, 61 (2017), 577-583.
    25. Decomposing graphs into paths and trees. With T. Klimošová, Electronic Notes in Discrete Mathematics, 61 (2017), 751-757.
    26. On the complexity of partial derivatives. With I. Garcia-Marco, P. Koiran and T. Pecatte, STACS 2017.
    27. 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.
    28. The Erdős-Hajnal conjecture for long holes and antiholes. With M. Bonamy and N. Bousquet, SIAM J. Discrete Math., 30 (2016), 1159-1164.
    29. 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.
    30. Isolating highly connected induced subgraphs. With I. Penev and N. Trotignon, SIAM J. Discrete Math., 30 (2016), 592-619.
    31. VC-dimension and Erdős-Pósa property of graphs. With N. Bousquet, Discrete Mathematics, 338 (2015), 2302-2317.
    32. 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.
    33. The Erdős-Hajnal conjecture for paths and antipaths. With N. Bousquet and A. Lagoutte, J. Combin. Theory Ser. B, 113 (2015), 261-264.
    34. A tau-conjecture for Newton polygons. With P. Koiran, N. Portier and S. Tavenas, Foundations of Computational Mathematics, 15 (2015), 185-197.
    35. Excluding clocks. With P. Aboulker and Z. Li, Electronic Notes in Discrete Mathematics, 50 (2015), 103-108.
    36. Cliques versus independent sets. With N. Bousquet and A. Lagoutte, European J. Combin., 40 (2014), 73-92.
    37. A note on the minimum distance of quantum LDPC codes. With N. Delfosse and Z. Li, MFCS 2014.
    38. Parameterized algorithm for weighted independent set problem in bull-free graphs. With N. Trotignon and K. Vuskovic, WG 2014, Algorithmica, 77 (2017), 619-641.
    39. Disjoint circuits in tournaments, beyond the Bermond-Thomassen conjecture. With J. Bang-Jensen and S. Bessy, J. Graph Theory, 75 (2014), 284-302.
    40. 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.
    41. 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.
    42. Symmetric determinantal representations in characteristic 2. With B. Grenet and T. Monteil, Linear Algebra and its Applications, 439 (2013), 1364--1381.
    43. Oriented trees in digraphs. With L. Addario-Berry, F. Havet, C. Linhares Sales and B. Reed, Discrete Mathematics, 313 (2013), 967--974.
    44. 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.
    45. A stability theorem on fractional covering of triangles by edges. With P. Haxell and A. Kostochka, European J. Combin., 33 (2012), 799--806.
    46. Cyclic orderings and cyclic arboricity of matroids. With J. van den Heuvel, J. Combin. Theory Ser. B, 102 (2012), 638--646.
    47. Scott's induced subdivision conjecture for maximal triangle-free graphs. With N. Bousquet, Combinatorics, Probability and Computing, 21 (2012), 512--514.
    48. Parameterized domination in circle graphs. With N. Bousquet, D. Gonçalves, G. Mertzios, C. Paul and I. Sau, WG 2012, Theory Comput. Syst., 54 (2014), 45--72.
    49. Packing and covering triangles in K4-free planar graphs. With P. Haxell and A. Kostochka, Graphs and Combinatorics, 28 (2012), 653--662.
    50. The domination number of grid graphs. With D. Gonçalves, A. Pinlou and M. Rao, SIAM J. of Discrete Maths, 25 (2011), 1443--1453.
    51. Linear vertex-kernels through conflict packing: Application to FAST and RTI problems. With C. Paul and A. Perez, MFCS 2011, J. Comput. Syst. Sci., 82 (2016), 366-379.
    52. Multicut is FPT. With N. Bousquet and J. Daligault, STOC 2011, SIAM J. Comput., 47 (2018), 166-207.
    53. Hitting and harvesting pumpkins. With G. Joret, C. Paul, I. Sau and S. Saurabh, ESA 2011, SIAM J. Discrete Math., 28 (2014), 1363-1390.
    54. Realizing disjoint degree sequences of span two: a solvable discrete tomography problem. With F. Guíñez and M. Matamala, Discrete Applied Mathematics, 159 (2011), 23--30.
    55. 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, J. Comput. Syst. Sci., 80 (2014), 687-696.
    56. 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).
    57. Partitions versus sets: A case of duality. With L. Lyaudet and F. Mazoit, European J. Combin., 31 (2010), 681--687.
    58. 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.
    59. WDM and directed star arboricity. With O. Amini, F. Havet and F. Huc, Combinatorics, Probability and Computing, 19 (2010), 161--182.
    60. Well-quasi-order of relabel functions. With J. Daligault and M. Rao, ROGICS 2008, Order, 27 (2010), 301--315.
    61. A quadratic kernel for feedback vertex set, SODA 2009, ACM Transactions on Algorithms, 6 (2010), Art. 32, 8 pp.
    62. Partition submodular functions. With O. Amini, F. Mazoit and N. Nisse, Discrete Mathematics, 309 (2009), 6000--6008.
    63. On finding directed trees with many leaves. With J. Daligault, IWPEC 2009.
    64. Kernels for Feedback Arc Set in Tournaments. With S. Bessy, F. Fomin, S. Gaspers, C. Paul, A. Perez and S. Saurabh, FSTTCS 2009, J. Comput. Syst. Sci., 77 (2011), 1071--1078.
    65. A 3k kernel for Maximum Internal Spanning Tree. With F. Fomin, S. Gaspers and S. Saurabh, ISAAC 2009, J. Comput. Syst. Sci., 79 (2013), 1--6.
    66. Spanning galaxies in digraphs. With D. Gonçalves, F. Havet and A. Pinlou, EUROCOMB 2009, Discrete Applied Mathematics, 160 (2012), 744--754.
    67. A polynomial kernel for Multicut In Trees. With N. Bousquet, J. Daligault and A. Yeo, STACS 2009.
    68. Kernel bounds for disjoint cycles and disjoint paths. With H. Bodlaender and A. Yeo, ESA 2009, Theoretical Computer Science, 412 (2011), 4570--4578.
    69. Complexity of (p,1)-total labelling. With F. Havet, Discrete Applied Mathematics, 157 (2009), 2859--2870.
    70. Guarding art galleries: The extra cost for sculptures is linear. With L. Addario-Berry, O. Amini and J.S. Sereni, SWAT 2008, LNCS, 5124 (2008), 41--52.
    71. The Hoàng-Reed conjecture holds for tournaments. With F. Havet and A. Yeo, Discrete Mathematics, 308 (2008), 3412--3415.
    72. 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.
    73. Branchwidth of graphic matroids. With F. Mazoit, Surveys in combinatorics 2007, London Math. Soc. Lecture Note Ser., 346 (2007), 275--286.
    74. Paths with two blocks in n-chromatic digraphs. With L. Addario-Berry and F. Havet, J. Combin. Theory Ser. B, 97 (2007), 620--626.
    75. Graphs with large girth not embeddable in the sphere. With P. Charbit, Combinatorics, Probability and Computing, 16 (2007), 829--832.
    76. 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.
    77. Spanning a strong digraph by α circuits: A proof of Gallai's conjecture. With S. Bessy, Combinatorica, 27 (2007), 659--667.
    78. Partitions and orientations of the Rado graph. With R. Diestel, I. Leader and A. Scott, Trans. Amer. Math. Soc., 359 (2007), 2395--2405.
    79. Total domination of graphs and small transversals of hypergraphs. With A. Yeo, Combinatorica, 27 (2007), 473--487.
    80. Density conditions for triangles in multipartite graphs. With A. Bondy, J. Shen and C. Thomassen, Combinatorica, 26 (2006), 121--131.
    81. The Categorical Product of two 5-chromatic digraphs can be 3-chromatic. With S. Bessy, Discrete Mathematics, 305 (2005), 344--346.
    82. 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.
    83. Three min-max theorems concerning cyclic orders of strong digraphs.. With S. Bessy, IPCO 2004, LNCS, 3064 (2004), 132--138.
    84. The C3-structure of tournaments. With A. Boussairi, P. Ille and G. Lopez, Discrete Mathematics, 277 (2004), 29--43.
    85. Small degree out-branchings. With J. Bang-Jensen and A. Yeo, J. Graph Theory, 42 (2003), 297--307.
    86. Highly connected hypergraphs containing no two edge-disjoint spanning connected subhypergraphs. With J. Bang-Jensen, Discrete Applied Mathematics, 131 (2003), 555--559.
    87. 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.
    88. Generalized pigeonhole properties of graphs and oriented graphs. With A. Bonato, P.J. Cameron and D. Delic, European J. Combin., 23 (2002), 257--274.
    89. Covering a strong digraph by α-1 disjoint paths: a proof of Las Vergnas' conjecture, J. Combin. Theory Ser. B, 83 (2001), 331--333.
    90. Countable α-extendable graphs. With J.L. Rullière, Discrete Mathematics, 239 (2001), 53--67.
    91. 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.
    92. Oriented Hamiltonian paths in tournaments: a proof of Rosenfeld's conjecture. With F. Havet, J. Combin. Theory Ser. B, 78 (2000), 243--273.
    93. On better-quasi-ordering countable series-parallel orders, Trans. Amer. Math. Soc., 352 (2000), 2491--2505.
    94. 2-partition-transitive tournaments. With B. Guiduli, A. Gyárfás and P. Weidl, J. Combin. Theory Ser. B, 72 (1998), 181--196.
    95. Indivisibility and α-morphisms, European J. Combin., 18 (1997), 445--454.
    96. Relations infinies indécomposables critiques. With L. Rigollet, C. R. Acad. Sci. Paris Sér. I, 324 (1997), 249--252.
    97. 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.
    98. Belordre des série-parallèles dénombrables. C. R. Acad. Sci. Paris Sér. I, 317 (1993), 909--912.