Publications
Upcoming work
- The Canadian Traveller Problem on outerplanar graphs. With L. Beaudou, P. Bergé, V. Chernyshev, A. Dailly, Y. Gerard, V. Limouzy and L. Pastor. Submitted [ArXiV]
- Local certification of geometric graph classes. With O. Defrain, L. Esperet, P. Morin, JF. Raymond. Submitted [ArXiV]
- (2K2, W4)-free graphs are ω +1 colorable. With N. Bousquet. In preparation.
Journal papers
- Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly. With L. Beaudou, C. Brosse, O. Defrain, F. Foucaud, V. Limouzy, and L. Pastor. Discrete Mathematics & Theoretical Computer Science, 25(2), 2024 [DOI | ArXiV]
- Efficient enumeration of maximal split subgraphs and sub-cographs and related classes. With C. Brosse, V. Limouzy, A. Mary and L. Pastor. Discrete Applied Mathematics, 345:34-51, 2024 [DOI| ArXiV]
- On Vizing’s edge colouring question. With M. Bonamy, O. Defrain, T. Klimošová and J. Narboni. Journal of Combinatorial Theory, series B,159:126-139, 2023 [DOI | ArXiv]
- Revisiting a theorem by Folkman on graph colouring. With M. Bonamy, P. Charbit, O. Defrain, G. Joret, V. Limouzy, L. Pastor, and J.-S. Sereni. Electronic Journal of Combinatorics, 27(1), P1.56, 2020 [DOI | ArXiv]
- Decomposition techniques for the Clique-Stable set Separation problem. With Nicolas Bousquet, Frédéric Maffray and Lucas Pastor. Discrete Mathematics, 341(5):1492-1501, 2018. [DOI | ArXiv]
- Coloring graphs with no even hole of length at least 6 : the triangle-free case. Electronic Journal of Combinatorics, 24(3), #P3.8, 2017. [DOI | ArXiv].
- Coloring perfect graphs with bounded clique number. With Maria Chudnovsky, Paul Seymour and Sophie Spirkl. Journal of Combinatorial Theory, Series B, 122:757-775, 2017 . [DOI | ArXiv]
- Clique Stable separation in perfect graphs with no balanced skew partition. With Théophile Trunck. Discrete Mathematics, 339(6):1809-1825, 2016. [DOI | ArXiv]
- Identifying codes and VC-dimension. With Nicolas Bousquet, Zhentao Li, Aline Parreau and Stéphan Thomassé. SIAM Journal of Discrete Mathematics, 29(4):2047-2064, 2015. [DOI | ArXiv] (A short conference version appeared in BGW’14).
- Strong edge-coloring of (3, delta)-bipartite graphs. With Julien Bensmail and Petru Valicov. Discrete Mathematics, 339(1):391-398, 2015. [DOI | ArXiv]
- The Erdös-Hajnal conjecture for paths and antipaths. With Nicolas Bousquet and Stéphan Thomassé. Journal of Combinatorial Theory, series B, 113:261-264, 2015. [DOI | ArXiv]
- Clique versus Independent Set. With Nicolas Bousquet and Stéphan Thomassé. European Journal of Combinatorics, 40:73-92, 2014. [DOI | ArXiv]
- Flooding games on graphs. With Mathilde Noual and Eric Thierry. Discrete Applied Mathematics, 164(2):532-538, 2014. [DOI | HAL]
Conference papers
- Composing extended top-down tree transducers. With Fabienne Braune, Daniel Quernheim, Andreas Maletti. In EACL 2012:808-817 [URL]
- Alternative method for Hamilton-Jacobi PDEs in image processing. WIth Hadrien Salat, Corinne Vachier. In Proc. SPIE 7870, Image Processing: Algorithms and Systems IX, 787010, 2011. [DOI]
Book chapter
- Survey: Weighted Extended Top-Down Tree Transducers Part III – Composition. With Andreas Maletti. In Algebraic Foundations in Computer Science, 272-308, 2011 (invited lecture). [DOI]
Unpublished
- The complexity of Shortest Common Supersequence for inputs with no identical consecutive letters, with Sébastien Tavenas. [ArXiv]
- Master 2 Internship with Stéphan Thomassé (Team MC2, LIP , ENS Lyon): Quasi-P versus P (view through the Alon-Saks-Seymour conjecture, and the Clique versus Stable Set problem). My report and my slides.
- Master 1 Internship with Andreas Maletti (IMS, Universität Stuttgart): Composition of extended top-down tree transducers. My report and my slides.
- Licence 3 Internship with Eric Thierry (Team MC2, LIP , ENS Lyon): Jeux d’inondations dans les graphes. My report (in french) and my slides (in french). Partial translation of my report (in english) on arXiv.
Some talks:
| Date | Place & Title | Slides |
|---|---|---|
| 2023 – Apr 5 | GT Graphes selected speaker, Journées Nationales du GDR-IM, Paris | here |
| Enumeration algorithms in graphs | ||
| 2021 – Nov 17 | Invited speaker at Journées Graphes et Algorithmes ’21, online | here |
| Algorithmes d’énumération de réparations de graphes | ||
| 2018 – Nov 9 | 30th anniversary of the LIP, ENS Lyon | here |
| Graphes : structure et algorithmes | ||
| 2018 – June 4 | Mini-symposium on Graph Coloring SIAM conference on Discrete Maths – Denver, USA | here |
| Coloring (2K2, W4)-free graphs | ||
| 2017 – Oct 3 | Reading group « Distributed Algorithms and Structures », JCRAA – G-SCOP, Grenoble | here |
| Lower bounds, based on Göös, Hirvonen and Suomela work | ||
| 2016 – Nov 17 | JGA (Journées Graphes et Algorithmes) – LAMSADE, Paris Charles Delorme Prize | here |
| Coloring perfect graphs with bounded clique number | ||
| 2015 – Oct 15 | Discrete Mathematics Seminar, Princeton University | here |
| Clique-Stable set Separation | ||
| 2015 – July 3 | GOAL Seminar, LIRIS, University Lyon 1 | here |
| Coloring graphs with no even holes of length at least 6: the triangle-free case | ||
| 2014 – Dec 4 | G-SCOP Seminar, University of Grenoble | here |
| From extended formulations of polytopes to the Clique-Stablet Set separation | ||
| 2014 – Nov 19 | Conference BGW’2014, Bordeaux | here |
| Identifying codes and VC-dimension | ||
| 2014 – Nov 14 | 2nd Lyon-Sao Paulo Research Workshop, Sao Paulo, Brazil | here |
| Extended formulations of polytopes and Communication Complexity | ||
| 2013 – Dec 19 | Bertinoro Workshop on Algorithms and Graphs, Bertinoro, Italy | here |
| Clique Stable Set separation in perfect graphs with no balanced skew partition | ||
| 2013 – Nov 14 | JGA (Journées Graphes et Algorithmes) – LRI, Orsay | here |
| Clique Stable Set separation in perfect graphs with no balanced skew-partition | ||
| 2013 – April 8 | EJC (Ecole Jeunes Chercheurs) – University of Perpignan | here |
| 10 minutes to understand the Clique-Stable set Separation | ||
| 2012 – Nov 15 | JGA (Journées Graphes et Algorithmes) – LIMOS, Clermont-Ferrand | here |
| Quasi P versus P: The Polynomial Alon-Saks- Seymour conjecture and related problems |