Marthe Bonamy
Tel +33 (0)5 40 00 60 88
Office 305

CNRS researcher at LaBRI in Bordeaux (since December 2015).
Member of the team CombAlgo and more specifically of the group Graphes et Optimisation.

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

CV (pdf)

Contact Information

Research interests




Research interests:

I study combinatorics, and more precisely graph theory.

I defended in February 2015 a PhD thesis about the
discharging method, and more exactly about the global discharging method, a variation introduced by Borodin et al, where the discharging rules can take structures of unbounded size into account. This thesis was prepared in the ALgorithms, Graphs and COmbinatorics group of the LIRMM (Montpellier, France). More details here.

In 2010, during the first year of my masters, I had the opportunity to do an eight-week internship in the ACiD group of the School of Engineering and Computing Sciences, in Durham, United Kingdom. There, I worked with Daniël Paulusma and Matthew Johnson on the problem of graph recoloring. I still work on graph reconfiguration problems now and then, and organized a mini-symposium on that topic in SIAM DM'16 (Atlanta).

Luke Postle and I are the PIs of a Joint Bordeaux-Waterloo Research Grant (Colouring and Probabilities) for 2016-2017. I was a member of the ANR Project EGOS (Embedded Graphs and their Oriented Structures, 2012 - 2015) and of a PHC Proteus Project (Coloring graphs on surfaces, 2014-2015).


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

Recent Talks:

  • GT Algorithmique distribuée, LaBRI, Bordeaux, 10/2016: An overview of discharging methods.
  • SiWAG, Polignano, 09/2016: Kempe equivalence of colourings, joint work with N. Bousquet, C. Feghali and M. Johnson.
  • Séminaire de Mathématiques Discrètes, Grenoble, 09/2016: Tight lower bounds for the complexity of multicoloring, joint work with Ł. Kowalik, M. Pilipczuk, A. Socała, M. Wrochna.
  • Combinatorics Seminar, Birmingham, 07/2016: Kempe equivalence of colourings, joint work with N. Bousquet, C. Feghali and M. Johnson.
  • SIAM Conference on Discrete Mathematics, Atlanta, 06/2016: Reed's Conjecture and Strong Edge Coloring, joint work with T. Perrett and L. Postle.
  • Complex Networks Seminar, LIP6, Paris, 06/2016: Kempe equivalence of colourings, joint work with N. Bousquet, C. Feghali and M. Johnson.
  • ZAA seminar, Warsaw, 05/2016: Reed's Conjecture and Strong Edge Coloring, joint work with T. Perrett and L. Postle.
  • Scottish Combinatorics Meeting, Glasgow, 04/2016: Reed's conjecture and strong edge coloring, joint work with T. Perrett and L. Postle, invited talk.
  • Barbados Graph Theory workshop, Holetown, 03/2016: Progress on Reed's chi-Delta-omega conjecture (with L. Postle), joint work with T. Perrett and L. Postle.
  • Graph theory seminar, Waterloo, 03/2016: Gallai's path decomposition conjecture, joint work with T. Perrett.
  • GT Graphes&Optimisation, LaBRI, Bordeaux, 01/2016: Coloration aléatoire de graphes peu denses, joint work with T. Perrett and L. Postle.
  • DMO-seminar, McGill University, Montréal, 11/2015: Kempe equivalence of colourings, joint work with N. Bousquet, C. Feghali and M. Johnson.
  • Tutte Colloquium, Waterloo, 10/2015: FPT meets discharging, based on joint work with D. Cranston, Ł. Kowalik and L. Postle.
  • Graph theory seminar, Waterloo, 10/2015: Kempe equivalence of colourings, joint work with N. Bousquet, C. Feghali and M. Johnson.
See here for older talks.

Where you might see or have seen me: 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, Dan Cranston,
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, Natasha Morrison, Daniel Paulusma, Guillem Perarnau, Thomas Perrett, Luke Postle, Jakub Przybyło, Michael Rao, Riste Škrekovski, Stéphan Thomassé, Carsten Thomassen, Petru Valicov, Lena Yuditsky.
Visitors: Hervé Hocquard, Tereza Klimošova, Dan Kráľ, Aurélie Lagoutte, Borut Lužar, Natasha Morrison, Lucas Pastor, Thomas Perrett, Riste Škrekovski, Marcin Wrochna.


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.
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.


Some fellow PhD students at LIRMM: Boris Albar, Julien Baste, Nicolas Bousquet, Valentin Garnero, Guillaume Guégan, Jean-Florent Raymond, Kévin Sol, Guillaume Tisserant.

Some students I was happy to get to know at ÉNS Lyon: Guillaume Allais, Guillaume Aupy, Hélène Badouin, Antoine Bérut, Nicolas Bonifas, Sylvain Dailler, Lee Dinetan, Hugo Férée, Benjamin Hellouin de Menibus, Yann Hourdel, Guillaume Iooss, Adriane Kaïchouh, Hugo Labrande, François Le Maître, Laetitia Lemoine, Jean-Marie Madiot, Sébastien Martineau, Lucie Martinet, Mathilde Mousset, Vincent Neiger, Pierre-Marie Pédrot, Matthieu Perrinel, Vincent Picard, Thomas Picchetti, Amaury Pouly, Sylvain Prigent, Jonathan Protzenko, Mikaël Rabie, Gabriel Renault, Philippe Robert, Sébastien Tavenas, Antoine Taveneaux, Théophile Trunck, Jill-Jênn Vie, Coline Wiatrowski.

Some teachers I was lucky to have (non-exhaustively): Nicolas Brisebarre, Alain Chamaraux, Florent de Dinechin, Guillaume Hanrot, Daniel Hirschkoff, Stéphane Legros, Laëtitia Sansonetti, Grégoire Taviot, Éric Thierry, Michael Verniquet.