Bienvenue chez Stéphan Thomassé

Je suis professeur d'informatique à l'université Montpellier II.
Je fais partie de l'équipe Algorithmes, Graphes et Combinatoire AlGCo du laboratoire LIRMM.

  • Contact et Vita :
    Adresse: LIRMM, 161 rue Ada, 34392 Montpellier Cedex 5 - France
    Tél.: 04 67 41 86 05. Fax: 04 67 41 85 00. Bureau: E.3.21
    Mail: monnom au lirmm.fr
    Curriculum vitae: In french . En anglais.

  • Enseignement :
    FLIN408 Analyse d'algorithmes.
    FLIN503 Algorithmes de graphes .
    FLIN609 Programmation linéaire.
    UMINR341 Algorithmique combinatoire.

  • Séminaires et Groupes de Travail :
    GT Graphes du GDR IM.
    Journées Combinatoire et Algorithmes du Littoral Méditerranéen (JCALM).
    Séminaire d'optimisation discrète du LIRMM.
    Groupe de travail de l'équipe AlGCo.
    Conférences et Workshops auxquels j'ai assisté.

  • Selected Problems : Tentez votre chance.

  • Publications :
    Mes thèmes de recherche au sens large sont la théorie des graphes, l'optimisation combinatoire et l'algorithmique.
    1. Coloring dense graphs via VC-dimension. Avec T. Łuczak, en préparation.
    2. Cyclic Orderings and Cyclic Arboricity of Matroids. Avec J. van den Heuvel, soumis.
    3. The Domination Number of Grid Graphs. Avec D. Gonçalves, A. Pinlou et M. Rao, en préparation.
    4. Star Packing and Crown Reduction. Avec J. Daligault, R. Giroudeau, J.C. König et G. Simonin, en préparation.
    5. Stability of Digraphs and Minimum Spanning Handles. Avec S. Bessy, en préparation.
    6. Kernels for Feedback Arc Set in Tournaments. Avec S. Bessy, F. Fomin, S. Gaspers, C. Paul, A. Perez et S. Saurabh, FSTTCS 2009.
    7. A 3k kernel for Maximum Internal Spanning Tree. Avec F. Fomin, S. Gaspers et S. Saurabh, ISAAC 2009.
    8. Partitions versus sets: A case of duality. Avec L. Lyaudet et F. Mazoit, à paraître dans European J. Combin..
    9. Realizing disjoint degree sequences of span two: a solvable discrete tomography problem. Avec F. Guíñez et M. Matamala, soumis.
    10. Partitioning a graph into a cycle and an anticycle: a proof of Lehel's conjecture. Avec S. Bessy, à paraître dans J. Combin. Theory Ser. B.
    11. Partition submodular functions. Avec O. Amini, F. Mazoit et N. Nisse, Discrete Math., 309 (2009), 6000--6008.
    12. WDM and directed star arboricity. Avec O. Amini, F. Havet et F. Huc, à paraître dans Combinatorics, Probability and Computing.
    13. Dense triangle-free graphs are four colorable: A solution to the Erdös-Simonovits problem. Avec S. Brandt, à paraître dans J. Combin. Theory Ser. B.
    14. On finding directed trees with many leaves. Avec J. Daligault, IWPEC 2009.
    15. The spanning galaxy problem. Avec D. Gonçalves, F. Havet et A. Pinlou, EUROCOMB2009, soumis en revue.
    16. A polynomial kernel for Multicut In Trees. Avec N. Bousquet, J. Daligault et A. Yeo, STACS09.
    17. Kernel bounds for disjoint cycles and disjoint paths. Avec H. Bodlaender et A. Yeo, ESA '09.
    18. A quadratic kernel for feedback vertex set, SODA 2009, à paraître dans ACM Transactions on Algorithms.
    19. Complexity of (p,1)-total labelling. Avec F. Havet, Discrete Applied Math., 157 (2009), 2859--2870.
    20. Guarding art galleries: The extra cost for sculptures is linear. Avec L. Addario-Berry, O. Amini et J.S. Sereni, SWAT 2008, LNCS, 5124 (2008), 41--52.
    21. Well-quasi-order of relabel functions. Avec J. Daligault et M. Rao, ROGICS 08, soumis en revue.
    22. The Hoàng-Reed conjecture holds for tournaments. Avec F. Havet et A. Yeo, Discrete Math., 308 (2008), 3412--3415.
    23. Finding a vector orthogonal to roughly half a collection of vectors. Avec P. Charbit, E. Jeandel, P. Koiran et S. Périfel, J. of Complexity, 24 (2008), 39--53.
    24. Branchwidth of graphic matroids. Avec F. Mazoit, Surveys in combinatorics 2007, London Math. Soc. Lecture Note Ser., 346 (2007), 275--286.
    25. Paths with two blocks in n-chromatic digraphs. Avec L. Addario-Berry et F. Havet, J. Combin. Theory Ser. B, 97 (2007), 620--626.
    26. Graphs with large girth not embeddable in the sphere. Avec P. Charbit, Combinatorics, Probability and Computing, 16 (2007), 829--832.
    27. The minimum feedback arc set problem is NP-hard for tournament. Avec P. Charbit et A. Yeo, Combinatorics, Probability and Computing, 16 (2007), 1--4.
    28. Spanning a strong digraph by α circuits: A proof of Gallai's conjecture. Avec S. Bessy, Combinatorica, 27 (2007), 659--667.
    29. Partitions and orientations of the Rado graph. Avec R. Diestel, I. Leader et A. Scott, Trans. Amer. Math. Soc., 359 (2007), 2395--2405.
    30. Total domination of graphs and small transversals of hypergraphs. Avec A. Yeo, Combinatorica, 27 (2007), 473--487.
    31. Density conditions for triangles in multipartite graphs. Avec A. Bondy, J. Shen et C. Thomassen, Combinatorica, 26 (2006), 121--131.
    32. The Categorical Product of two 5-chromatic digraphs can be 3-chromatic. Avec S. Bessy, Discrete Math., 305 (2005), 344--346.
    33. Convex cones and SAGBI bases of permutation invariants. Avec N. Thiéry, Invariant theory in all characteristics, CRM Proc. Lecture Notes, 35 (2004), 259--263.
    34. Three min-max theorems concerning cyclic orders of strong digraphs. Avec S. Bessy, I.P.C.O., Lecture Notes in Comput. Sci., 3064 (2004), 132--138.
    35. The C3-structure of tournaments. Avec A. Boussairi, P. Ille et G. Lopez, Discrete Math., 277 (2004), 29--43.
    36. Small degree out-branchings. Avec J. Bang-Jensen et A. Yeo, J. Graph Theory, 42 (2003), 297--307.
    37. Highly connected hypergraphs containing no two edge-disjoint spanning connected subhypergraphs. Avec J. Bang-Jensen, Discrete Appl. Math., 131 (2003), 555--559.
    38. Every strong digraph has a spanning strong subgraph with at most n+2α-2 arcs. Avec S. Bessy, J. Combin. Theory Ser. B, 87 (2003), 289--299.
    39. Generalized pigeonhole properties of graphs and oriented graphs. Avec A. Bonato, P.J. Cameron et D. Delic, European J. Combin., 23 (2002), 257--274.
    40. Covering a strong digraph by α-1 disjoint paths: a proof of Las Vergnas' conjecture, J. Combin. Theory Ser. B, 83 (2001), 331--333.
    41. Countable α-extendable graphs. Avec J.L. Rullière, Discrete Math., 239 (2001), 53--67.
    42. Median orders of tournaments: a tool for the second neighborhood problem and Sumner's conjecture. Avec F. Havet, J. Graph Theory, 35 (2000), 244--256.
    43. Oriented Hamiltonian paths in tournaments: a proof of Rosenfeld's conjecture. Avec F. Havet, J. Combin. Theory Ser. B, 78 (2000), 243--273.
    44. On better-quasi-ordering countable series-parallel orders, Trans. Amer. Math. Soc., 352 (2000), 2491--2505.
    45. 2-partition-transitive tournaments. Avec B. Guiduli, A. Gyárfás et P. Weidl, J. Combin. Theory Ser. B, 72 (1998), 181--196.
    46. Indivisibility and α-morphisms, European J. Combin., 18 (1997), 445--454.
    47. Relations infinies indécomposables critiques. Avec L. Rigollet, C. R. Acad. Sci. Paris Sér. I, 324 (1997), 249--252.
    48. Hypomorphie et inversion locale entre graphes. Avec A. Boussairi, P. Ille et G. Lopez, C. R. Acad. Sci. Paris Sér. I, 317 (1993), 125--128.
    49. Belordre des série-parallèles dénombrables, C. R. Acad. Sci. Paris Sér. I, 317 (1993), 909--912.