Marthe Bonamy



marthe.bonamy@u-bordeaux.fr
Tel +33 (0)5 40 00 35 13
Office 119

CNRS researcher at LaBRI in Bordeaux.
Member of the team CombAlgo,
head of the group Graphes et Optimisation and member of the group AlgoDist.

Université de Bordeaux, LaBRI
351, cours de la Libération, CS 10004
F-33405 Talence Cedex - France

CV (pdf)

Contact Information

Current situation

Publications

Talks

Teaching

Other

Current Situation:

I study combinatorics, and more precisely graph theory. I am notably interested in planar graphs, algorithms, graph decompositions, in particular graph recoloring and other reconfiguration problems.

I am a member of the ANR Project
ENEDISC (ENergy Efficient DIStributed Computing, 2024 - 2027).

I am currently supervising three PhD students: Paul Bastide (Local structures in Combinatorics: reconstruction, saturation, spreadness and universality, 2022-2025, co-supervised with Carla Groenland), Timothé Picavet (Distributed algorithms and local structures in graphs, 2023-2026, co-supervised with Cyril Gavoille) and Romain Bourneuf (Graph compression and reconstruction, 2024-2027, co-supervised with Stéphan Thomassé). My first PhD student Théo Pierron (Induction schemes: from languages separation to graph colorings, 2015-2019, co-supervised with Éric Sopena and Marc Zeitoun) is currently an associate professor in Lyon. My second and third PhD students Paul Ouvrard (Combinatorial reconfiguration, 2017-2021, co-supervised with Paul Dorbec and Cyril Gavoille) and Alexandre Blanché (Decomposing a graph into elementary structures, 2018-2021, co-supervised with Nicolas Bonichon), are currently in the private sector. My fourth PhD student Jonathan Narboni (Homomorphisms, colorings and structural properties of graphs, 2019-2022, co-supervised with Feri Kardoš and Éric Sopena) is currently ATER in Bordeaux. My fifth PhD student Claire Hilaire is currently a postdoc in Koper. My sixth PhD student Clément Legrand-Duchesne (Exploring the space of graph colorings, 2021-2024, co-supervised with Vincent Delecroix) is currently a postdoc in Krakow.

I am the vice-Editor-in-chief of the European Journal of Combinatorics since January 2021, a member of the Board of Editors of Discrete Mathematics since January 2021, an editor of Innovations in Graph Theory since its launch in August 2023, and an associate editor of the SIAM Journal of Discrete Mathematics since January 2024. I am part of the scientific board of the GT COA, and of the steering commitee of STACS. Paul Bastide, Clara Marcille, Timothé Picavet and I are in charge of the Graphs & Optimization seminar at LaBRI.

Publications in Journals or Conferences:

(Currently not up to date, see my Google Scholar profile for more diligent updates than mine.)

In Journals:

In Conference proceedings:

You can also find my master thesis (whose journal version is "2-distance coloring of sparse graphs") and my PhD thesis.

Invited Talks:

  • EuroComb, Budapest, 08/2025.
  • One-Day Meeting in Combinatorics, Oxford, 05/2025.
  • Polish Combinatorial Conference 2024, Bedlewo, 09/2024.
  • 48th International Symposium on Mathematical Foundations of Computer Science “MFCS 2023”, Bor- deaux, 08/2023.
  • Belgian Graph Theory Conference, Ghent, 08/2023.
  • 3rd Workshop on Combinatorial Reconfiguration “CoRe”, affiliated with ICALP, Paderborn, 07/2023.
  • Foundations of Computational Mathematics “FOCM 2023” semi-plenary speaker in the Graph Theory and Combinatorics Workshop, Paris, 06/2023.
  • One-Day Meeting in Combinatorics, Oxford, 05/2023.
  • XVIII Summer School in Discrete Mathematics, Valparaiso, 01/2023.
  • 2nd Workshop Complexity and Algorithms "CoA 2022", Paris, 09/2022.
  • Slovenian Graph Theory conference, Maribor, 09/2022.
  • GROW 2022, Koper, 09/2022.
  • Discrete Mathematics Days 2022, Santander, 07/2022.
  • 10th anniversary of the Bézout Labex, Paris.
  • Journées de Géométrie Algorithmique, online.
  • British Combinatorics Conference, Durham (online), 07/2021, Decomposing the edges of a graph into simpler structures.
  • London Colloquia in Combinatorics, London (online), 05/2021, Exploring the space of colourings with Kempe changes.
  • Journées ALEA, Marseille (online), 03/2021, Recoloration de graphes.
  • Workshop on Graph Theory & Combinatorics in Thuringia, online, 07/2020, On Vizing’s Edge Colouring Question.
  • École Jeunes Chercheurs Informatique Mathématiques, online, 05/2020, Coloration et structure dans les graphes.
  • Quelles directions de recherche pour l'algorithmique en France ?, IRIF, 12/2019, Complexity of graph coloring.
  • Cycles & Colourings 2019, Novy Smokovec, 09/2019, Planar graphs: One graph to rule them all.
  • DIMEA Days 2019, Brno, 06/2020, Around Brooks' theorem.
  • CanaDAM 2019, Vancouver, 05/2020, Around Brooks' theorem.
  • 20èmes Journées Graphes et Algorithmes, Grenoble, 11/2018, Reconfiguration combinatoire.
  • 8th Cracow Conference on Graph Theory, Rytro, 09/2018, Coloring planar graphs: the distributed version.
  • 2nd Scottish Combinatorics Meeting, University of Glasgow, 04/2016, Reed's conjecture and strong edge coloring.
See here for more talks (not up-to-date).

Where you might see or have seen me: Bergen, 02/2025 || Paris, 02/2025 || Oberwolfach, 01/2025 || Dijon, 11/2024 || Paris, 10/2024 || Poznan, 09/2024 || Wittenberg, 09/2024 || Aussois, 05/2024 || Karlsruhe, 04/2024 || Clermont-Ferrand, 09/2023 || Ghent, 08/2023 || Paris, 06/2023 || Oxford, 05/2023 || Montpellier, 05/2023 || Warsaw, 02/2023 || Krakow, 02/2023 || Barbados, 12/2022 || Paris, 11/2022 || Utrecht, 11/2022 || Grenoble, 10/2022 || Paris, 09/2022 || Koper, 09/2022 || Maribor, 09/2022 || Lancaster, 07/2022 || Santander, 07/2022 || Banff, 05/2022 || Barbados, 03/2022 || Grenoble, 02/2022 || Lyon, 01/2022 || Oberwolfach, 01/2022 || Morelia, 12/2021 || Lyon, 11/2021 || Dagstuhl, 09/2021 || Bègles Graph Workshop on Adjacency Labelling Schemes, 06/2021 || Marseille, 06/2021 || Paris, 10/2020 || Pessac Graph Workshop on Cops&Robbers, 08/2020 || Workshop on Graph Theory & Combinatorics in Thuringia, online, 07/2020 || EJCIM'20, online, 04/2020 || Oxford, 03/2020 || GrR, Lyon, 02/2020 || Grenoble, 02/2020 || DATCORE 2020, Bordeaux, 02/2020 || Clermont-Ferrand, 12/2019 || Célébration médaille d'argent du CNRS, Paris, 12/2019 || 21èmes Journées Graphes et Algorithmes, Bruxelles, 11/2019 || Bordeaux Graph Workshop, 10/2019 || Krakow, 10/2019 || Warsaw, 09-11/2019 || Cycles&Colorings, Novy Smokovec, 09/2019 || Pessac Graph Workshop on Reconfiguration, 08/2019 || Pessac Graph Workshop on Avoidable paths, 08/2019 || BCC'19, Birmingham, 07/2019 || Durham, 07/2019 || Graph Colouring: from Structure to Algorithms, Dagstuhl, 07/2019 || Gułtowy, 06/2019 || DIMEA Days, Brno, 06/2019 || Vancouver, 06/2019 || CanaDam'2019, Vancouver, 05/2019 || CoRe 2019, Aussois, 05/2019 || Oxford, 05/2019 || Workshop, Barbados, 04/2019 || Paris, 02/2019 || Clermont, 02/2019 || Lyon, 01/2019 || Oberwolfach, 01/2019 || Prague, 12/2018 || Grenoble, 11/2018 || 20èmes Journées Graphes et Algorithmes, Grenoble, 11/2018 || Helsinki, 11/2018 || Sendai, 10/2018 || Tokyo, 09/2018 || Cracow conference on Graph Theory, Krakow, 09/2018 || SW-graphs, Karlsruhe, 08/2018 || Pessac Graph Workshop on Enumeration, 08/2018 || Pessac Graph Workshop on Reconstruction, 08/2018 || Sakura meeting, Lyon, 07/2018 || ICGT, Lyon, 07/2018 || Waterloo, 06/2018 || SIAM Conference on Discrete Mathematics, Denver, 06/2018 || Richmond, 05/2018 || Sophia Antipolis, 05/2018 || Algorithm and Programming, Marseille, 05/2018 || Workshop, Barbados, 04/2018 || Réunion ANR Distancia, Marseille, 04/2018 || Journées Nationales GDR IM, Palaiseau, 04/2018 || Réunion ANR Descartes, Paris, 03/2018 || Varsovie, 03/2018 || Clermont-Ferrand, 02/2018 || Lyon, 01/2018 || Plzen, 12/2017 || Prague, 11/2017 || Berlin, 10/2017 || Grenoble, 10/2017 || Geometric and Structural Graph Theory, Banff, 08/2017 || Durham, 07/2017 || Glasgow, 07/2017 || BCC'17, Glasgow, 07/2017 || CanaDam'17, Toronto, 06/2017 || Waterloo, 06/2017 || Lyon, 05/2017 || Workshop, Cassis, 05/2017 || Oxford, 04/2017 || Grenoble, 04/2017 || Workshop, Barbados, 03/2017 || Rio de Janeiro, 03/2017 || Warsaw, 02/2017 || Prague, 11/2016 || New Trends in Graph Coloring, Banff, 10/2016 || Montpellier, 10/2016 || SiWAG, Polignano, 09/2016 || Grenoble, 09/2016 || Workshop on Shannon Capacity, Cassis, 09/2016 || Oxford, 08/2016 || Birmingham, 07/2016 || Glasgow, 07/2016 || Durham, 07/2016 || Copenhaguen, 06/2016 || SIAM Conference on Discrete Maths, Atlanta, 06/2016 || Paris, 06/2016 || Warsaw, 05/2016 || ÉPIT, Marseille, 05/2016 || Scottish Combinatorics Meeting, Glasgow, 04/2016 || Workshop, Barbados, 03/2016 || Waterloo, 03/2016 || 17èmes Journées Combinatoire et Algorithmes du Littoral Méditerranéen, Montpellier, 03/2016 || Montréal, 11/2015 || GT2015, Nyborg, 08/2015 || Glasgow, 07/2015 || Durham, 07/2015 || Oxford, 07/2015 || British Combinatorial Conference, Warwick, 07/2015 || Marseille, 06/2015 || Ljubljana, 06/2015 || Grenoble, 05/2015 || Waterloo, 05/2015 || Montréal, 04/2015 || Richmond, Virginia, 04/2015 || Workshop, Barbados, 03/2015 || Bordeaux, 03/2015 || Warsaw, 02/2015 || International Workshop on Graph Decomposition, Marseille, 01/2015 || Ljubljana, 12/2014 || Bordeaux, 11/2014 || Grenoble, 11/2014 || ICGT, Grenoble, 07/2014 || SIAM Conference on Discrete Maths, Minneapolis, 06/2014 || Lyon, 06/2014 || Warsaw, 05/2014 || LIAFA, Paris, 05/2014 || LIMOS, Clermont-Ferrand, 04/2014 || Workshop, Barbados, 03/2014 || Krakow, 03/2014 || Warsaw, 03/2014 || Sophia Antipolis, 01/2014 || Bratislava, 11/2013 || 15èmes Journées Graphes et Algorithmes, Orsay, 11/2013 || University of Birmingham, 11/2013 || University of Warwick, 11/2013 || 14èmes JCALM, Barcelona, 10/2013 || Eurocomb'13, Pisa, 09/2013 || Utrecht University, 08/2013 || SGT, Oléron, 06/2013 || 13èmes JCALM, Marseille, 06/2013 || WAM, Princeton, 05/2013 || Workshop, Barbados, 03/2013 || Bordeaux Graph Workshop, Bordeaux, 11/2012 || 14èmes JGA, Clermont-Ferrand, 11/2012 || Journées Egos, Montpellier, 10/2012 || 12èmes JCALM, Montpellier, 10/2012 || École Normale Supérieure de Lyon, 10/2012 || Cycles&Colorings, Slovakia, 09/2012 || Workshop on chi-bounded graph classes, Lyon, 03/2012 || 11èmes JCALM, Sophia Antipolis, 02/2012 || Journées Graphes et Structures Topologiques, Cévennes, 11/2011 || 13èmes JGA, Lyon, 11/2011 || Eurocomb'11, Budapest, 08/2011 || 10èmes JCALM, Barcelona, 06/2011 || 9èmes JCALM, Marseille, 02/2011 || A one day conference on structural graph theory, Paris, 01/2011 || The 2nd Coq workshop, Edinburgh, 07/2010 || Ecofac, Côtes d'Armor, 03/2010.

Visited: Nicolas Bousquet, Pierre Charbit, Dan Cranston, Konrad K. Dąbrowski, Zdeněk Dvořák, Louis Esperet, Carl Feghali, Fred Havet, Hervé Hocquard, Matthew Johnson, Ross Kang, Tereza Klimošova, Łukasz Kowalik, Dan Kráľ, Borut Lužar, Robert Lukot'ka, Kitty Meeks, Bojan Mohar, Natasha Morrison, Daniel Paulusma, Guillem Perarnau, Thomas Perrett, Marcin Pilipczuk, Michał Pilipczuk, Luke Postle, Jakub Przybyło, Michael Rao, Jean-Florent Raymond, Bruce Reed, Alex Scott, Riste Škrekovski, Stéphan Thomassé, Carsten Thomassen, Petru Valicov, Lena Yuditsky.
Visitors: Tara Abrishami, Guillaume Aubian, Valentin Bartier, Laurine Bénéteau, Stéphane Bessy, Édouard Bonnet, Fabio Botler, Stijn Cambie, Monika Csikos, James Davies, Lucas de Meyer, Oscar Defrain, Michelle Delcourt, Colin Geniet, Carla Groenland, Hannah Guggiari, Anna Gujgiczer, Marc Heinrich, Hervé Hocquard, Jedrzej Hodor, Freddie Illingworth, Tomas Kaiser, Tom Kelly, Eunjung Kim, Seog-Jin Kim, Tereza Klimošova, Dan Kráľ, Hoang La, Aurélie Lagoutte, William Lochet, Borut Lužar, Rose McCarty, Laura Merker, Laure Morelle, Natasha Morrison, Moritz Mühlenthaler, Carole Muller, Peter Nelson, Lucas Pastor, Jakub Pekarek, Thomas Perrett, Lucas Picasarri-Arrieta, Théo Pierron, Michał Pilipczuk, Luke Postle, Mikaël Rabie, Clément Rambaud, Jean-Florent Raymond, Shayla Redlin, Alex Roberts, Jean-Sébastien Sereni, Jozef Skokan, Riste Škrekovski, Evelyne Smith-Roberge, Stéphan Thomassé,
Alexandra Wesolek, Marcin Wrochna, Yelena Yuditsky.

Vitae:

Born in Normandie (Northern France) on the 2nd of October 1990.
Master degree from
École Normale Supérieure de Lyon in 2011.
PhD from Université Montpellier, prepared in the ALgorithms, Graphs and COmbinatorics group of the LIRMM, with Benjamin Lévêque and Alexandre Pinlou, defended on the 9th of February 2015 (more details here).
Three-month postdoc at University of Waterloo (september-november 2015) with Luke Postle.
Chargée de recherche CNRS (permanent research-only position) at LaBRI, Bordeaux (since 1st of December 2015).

Fluent in French (mother tongue) and English. Notions of German and Spanish.

Previous responsibilities:

Feri Kardoš and I organized the 2017 edition of the JGA. I was in a hiring committee for six Associate Professor positions (Clermont-Ferrand, Grenoble, Lyon, 2*Paris and Marseille). I was in the Program Committee of EuroComb 2019, FCT 2019, LAGOS 2019, MFCS 2019, IWOCA 2020, Algotel 2020, IPEC 2020, Algotel 2021, EuroComb 2021, STACS 2022, ICGT 2022, DISC 2022 and EuroComb 2023. I was the PC chair of CanaDAM 2021. I was an Associate Editor of Discrete Mathematics from April 2018 to December 2021, and an associate editor of Annals of Combinatorics from September 2019 to August 2022. I was twice in the NCN ST6 panel (Polish National Research Agency).

I was the PI of a PEPS grant DeKer (Discharging and Kernelization) for 2017. I was a member of the ANR Projects EGOS (Embedded Graphs and their Oriented Structures, 2012 - 2015), Distancia (Metric Graph Theory, 2017 - 2020), HoSiGra (Homomorphism on Signed Graphs, 2017 - 2020), and GrR (Graph Reconfiguration, 2019 - 2022), and of a PHC Proteus Project (Coloring graphs on surfaces, 2014-2015). Luke Postle and I were the PIs of a Joint Bordeaux-Waterloo Research Grant (Colouring and Probabilities) for 2016-2017, renewed for 2017-2018. I was the PI of a bilateral PHC project with Slovenia (Decompositions and coverings of graphs, 2019 - 2020, with Riste Škrekovški), with Czech Republic (Structural properties of graphs with no long paths, 2019 - 2020, with Tereza Klimošová), and with the Netherlands (Bridging between independent sets and colouring, 2020 - 2021, with Ross Kang). I was the PI of a multilateral project with South America (Structural and algorithmic graph theory, 2020 - 2021, with Flavia Bonomo and Maya Stein).

I supervised five master students: Paul Ouvrard (Reconfiguration of dominating sets under token sliding, co-supervised with Paul Dorbec, 2017), Alexandre Blanché (Gallai's path decomposition conjecture, co-supervised with Nicolas Bonichon, 2018), Clément Legrand-Duchesne (Kempe changes in degenerate graphs, co-supervised with Vincent Delecroix, 2021), Paul Bastide (Burning graphs, 2021) and Timothé Picavet (distributed domination in sparse classes, co-supervised with Alexandra Wesolek). I also supervised three 3rd-year Bachelor student: Romain Bourneuf (Fast algorithms for betweenness-centrality, 2021), Louann Coste (Firefighting in planar graphs, 2022, co-supervised with Claire Hilaire) and Benjamin Duhamel (Temporal graphs, 2023, co-supervised with Arnaud Casteigts and Timothée Corsini). Beside my own students, I was part of the PhD juries of the following. In France: Tien-Nam Lê (ENS de Lyon, 2018: examiner), Mehdi Khosravian (Université Paris-Dauphine, 2019: examiner), Ioannis Panagiotas (École Normale Supérieure de Lyon, 2020: examiner), Manon Philibert (Aix-Marseille Université, 2021: examiner), Hoang La (Université de Montpellier, 2022: examiner), Khaydar Nurligareev (Université Sorbonne Paris Nord, 2022: examiner), Nikolaos Melissinos (Université Paris Dauphine-PSL, 2022: examiner), Marco Caoduro (Université Grenoble Alpes, 2022: examiner), Guillaume Aubian (Université Paris Cité, 2023: examiner), Caroline Brosse (Université Clermont Auvergne, 2023: examiner), Lucas Picasarri-Arrieta (Université Côte d'Azur, 2024: examiner), Virginia Ardévol Martinez (Université Paris Dauphine, 2025: reviewer), Avinandan Das (Université Paris Cité, 2025: examiner). Abroad: Torstein Strømme (University of Bergen, 2020: opponent), Rikke Langhede (Technical University of Denmark, 2021: external examiner), Radek Hušek (Charles University, 2022: opponent), Nicolas Grelier (ETH Zurich, 2022: examiner), Felix Schröder (TU Berlin, 2023: examiner), Svein Høgemo (University of Bergen, 2025: opponent).

Popular science:

Hervé Hocquard and I were organizing the "Des enseignants dans les labos" operation (high school teachers get acquainted with the lab setting) in LaBRI in 2016--2018 (three editions). In 2020, Samuel Thibault and I organized a 2-day visit of LaBRI and INRIA Bordeaux Sud Ouest by 3rd-year Bachelor students and 1st-year Master students from ÉNS de Rennes. In 2018, I gave two talks on graph theory in a CIRM worshop for math teachers. In 2018, I gave a talk in the "Printemps de la mixité" workshop in LaBRI. I co-organized a 2-day visit of LaBRI and INRIA Bordeaux Sud Ouest by 3rd-year Bachelor students from ÉNS de Lyon (2017 and 2018 with Guillaume Aupy, 2019 and 2020 with Samuel Thibault, 2021 with Emmanuelle Saillard).