Stéphan Thomassé

Nouvelle Page / New Page

Professeur d'Informatique / Computer Science Professor
Université Montpellier II
Laboratoire / Laboratory LIRMM
Equipe / Team AlGCo

  • Contact & Vita :
    LIRMM, 161 rue Ada, 34095 Montpellier Cedex 5 - France
    Tél. : 04 67 41 86 05. Fax : 04 67 41 85 00. Bureau / Office : E.3.21
    Mail : name at lirmm.fr
    Curriculum vitae : In french . En anglais.

  • Enseignement / Teaching (2010-2011):
    FLIN408 Analyse d'algorithmes. FLIN503 Algorithmes de graphes. UMIN215 Algorithmique Géométrique.
    FLIN609 Programmation linéaire. FLMA614 Mathématiques du Web. UMINR341 Algorithmique combinatoire.

  • Séminaires / Seminars :
    Journées Combinatoire et Algorithmes du Littoral Méditerranéen (JCALM). GT Graphes du GDR IM.
    Séminaire d'optimisation discrète du LIRMM. Groupe de travail de l'équipe AlGCo.
    Conférences et Workshops passés et à venir.

  • Questions ouvertes / Open Problems : Tentez votre chance.

  • Publications : Mainly in Graph and Hypergraph Theory, Combinatorial Optimization and Algorithms.
    1. Scott's induced subdivision conjecture for maximal triangle-free graphs. With N. Bousquet, submitted.
    2. Simultaneously satisfying linear equations over F2. With R. Crowston, M. Fellows, G. Gutin, M. Jones, F. Rosamond and A. Yeo, submitted.
    3. VC-dimension and Erdös-Pósa property of graphs. With N. Bousquet, in preparation.
    4. Disjoint circuits in tournaments, beyond the Bermond-Thomassen conjecture. With J. Bang-Jensen and S. Bessy, submitted.
    5. Hitting and harvesting pumpkins. With G. Joret, C. Paul, I. Sau and S. Saurabh, ESA 2011.
    6. Stability of digraphs and minimum spanning handles. With S. Bessy, in preparation.
    7. Oriented trees in digraphs. With L. Addario-Berry, F. Havet, C. Linhares Sales and B. Reed, submitted.
    8. Tournaments and colouring. With E. Berger, K. Choromanski, M. Chudnovsky, J. Fox, M. Loebl, A. Scott and P. Seymour, submitted.
    9. The domination number of grid graphs. With D. Gonçalves, A. Pinlou and M. Rao, to appear in SIAM J. of Discrete Maths.
    10. Star packing and crown reduction. With J. Daligault, R. Giroudeau, J.C. König and G. Simonin, in preparation.
    11. Linear vertex-kernels through conflict packing: Application to FAST and RTI problems. With C. Paul and A. Perez, MFCS 2011.
    12. Edge growth in graph cubes. With M. DeVos, submitted.
    13. Coloring dense graphs via VC-dimension. With T. Łuczak, submitted.
    14. Packing and covering triangles in K4-free planar graphs. With P. Haxell and A. Kostochka, to appear.
    15. Multicut is FPT. With N. Bousquet and J. Daligault, STOC 2011.
    16. A stability theorem on fractional covering of triangles by edges. With P. Haxell and A. Kostochka, to appear.
    17. Cyclic orderings and cyclic arboricity of matroids. With J. van den Heuvel, to appear.
    18. Realizing disjoint degree sequences of span two: a solvable discrete tomography problem. With F. Guíñez and M. Matamala, Discrete Applied Math., 159 (2011), 23--30.
    19. Dense triangle-free graphs are four colorable: A solution to the Erdös-Simonovits problem. With S. Brandt, to appear in J. Combin. Theory Ser. B.
    20. 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 Mathematical Studies, 21 (2010).
    21. Partitions versus sets: A case of duality. With L. Lyaudet and F. Mazoit, European J. Combin., 31 (2010), 681--687.
    22. 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.
    23. WDM and directed star arboricity. With O. Amini, F. Havet and F. Huc, Combinatorics, Probability and Computing, 19 (2010), 161--182.
    24. Well-quasi-order of relabel functions. With J. Daligault and M. Rao, ROGICS 2008, Order, 27 (2010), 301--315.
    25. A quadratic kernel for feedback vertex set, SODA 2009, ACM Transactions on Algorithms, 6 (2010), Art. 32, 8 pp.
    26. Partition submodular functions. With O. Amini, F. Mazoit and N. Nisse, Discrete Math., 309 (2009), 6000--6008.
    27. On finding directed trees with many leaves. With J. Daligault, IWPEC 2009.
    28. Kernels for Feedback Arc Set in Tournaments. With S. Bessy, F. Fomin, S. Gaspers, C. Paul, A. Perez and S. Saurabh, FSTTCS 2009.
    29. A 3k kernel for Maximum Internal Spanning Tree. With F. Fomin, S. Gaspers and S. Saurabh, ISAAC 2009.
    30. Spanning galaxies in digraphs. With D. Gonçalves, F. Havet and A. Pinlou, EUROCOMB 2009, Electronic Notes in Discrete Mathematics, 34 (2009), 139-143.
    31. A polynomial kernel for Multicut In Trees. With N. Bousquet, J. Daligault and A. Yeo, STACS 2009.
    32. Kernel bounds for disjoint cycles and disjoint paths. With H. Bodlaender and A. Yeo, ESA 2009, to appear in Theoretical Computer Science (2011).
    33. Complexity of (p,1)-total labelling. With F. Havet, Discrete Applied Math., 157 (2009), 2859--2870.
    34. 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.
    35. The Hoàng-Reed conjecture holds for tournaments. With F. Havet and A. Yeo, Discrete Math., 308 (2008), 3412--3415.
    36. Finding a vector orthogonal to roughly half a collection of vectors. With P. Charbit, E. Jeandel, P. Koiran and S. Périfel, J. of Complexity, 24 (2008), 39--53.
    37. Branchwidth of graphic matroids. With F. Mazoit, Surveys in combinatorics 2007, London Math. Soc. Lecture Note Ser., 346 (2007), 275--286.
    38. Paths with two blocks in n-chromatic digraphs. With L. Addario-Berry and F. Havet, J. Combin. Theory Ser. B, 97 (2007), 620--626.
    39. Graphs with large girth not embeddable in the sphere. With P. Charbit, Combinatorics, Probability and Computing, 16 (2007), 829--832.
    40. 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.
    41. Spanning a strong digraph by α circuits: A proof of Gallai's conjecture. With S. Bessy, Combinatorica, 27 (2007), 659--667.
    42. Partitions and orientations of the Rado graph. With R. Diestel, I. Leader and A. Scott, Trans. Amer. Math. Soc., 359 (2007), 2395--2405.
    43. Total domination of graphs and small transversals of hypergraphs. With A. Yeo, Combinatorica, 27 (2007), 473--487.
    44. Density conditions for triangles in multipartite graphs. With A. Bondy, J. Shen and C. Thomassen, Combinatorica, 26 (2006), 121--131.
    45. The Categorical Product of two 5-chromatic digraphs can be 3-chromatic. With S. Bessy, Discrete Math., 305 (2005), 344--346.
    46. 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.
    47. Three min-max theorems concerning cyclic orders of strong digraphs.. With S. Bessy, IPCO 2004, LNCS, 3064 (2004), 132--138.
    48. The C3-structure of tournaments. With A. Boussairi, P. Ille and G. Lopez, Discrete Math., 277 (2004), 29--43.
    49. Small degree out-branchings. With J. Bang-Jensen and A. Yeo, J. Graph Theory, 42 (2003), 297--307.
    50. Highly connected hypergraphs containing no two edge-disjoint spanning connected subhypergraphs. With J. Bang-Jensen, Discrete Applied Math., 131 (2003), 555--559.
    51. 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.
    52. Generalized pigeonhole properties of graphs and oriented graphs. With A. Bonato, P.J. Cameron and D. Delic, European J. Combin., 23 (2002), 257--274.
    53. Covering a strong digraph by α-1 disjoint paths: a proof of Las Vergnas' conjecture, J. Combin. Theory Ser. B, 83 (2001), 331--333.
    54. Countable α-extendable graphs. With J.L. Rullière, Discrete Math., 239 (2001), 53--67.
    55. 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.
    56. Oriented Hamiltonian paths in tournaments: a proof of Rosenfeld's conjecture. With F. Havet, J. Combin. Theory Ser. B, 78 (2000), 243--273.
    57. On better-quasi-ordering countable series-parallel orders, Trans. Amer. Math. Soc., 352 (2000), 2491--2505.
    58. 2-partition-transitive tournaments. With B. Guiduli, A. Gyárfás and P. Weidl, J. Combin. Theory Ser. B, 72 (1998), 181--196.
    59. Indivisibility and α-morphisms, European J. Combin., 18 (1997), 445--454.
    60. Relations infinies indécomposables critiques. With L. Rigollet, C. R. Acad. Sci. Paris Sér. I, 324 (1997), 249--252.
    61. 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.
    62. Belordre des série-parallèles dénombrables. C. R. Acad. Sci. Paris Sér. I, 317 (1993), 909--912.