Id Photo
Pierre Aboulker

Département Informatique de l'ENS,
45 Rue d'Ulm,
75005 Paris - FRANCE.

Tel: A remplir

Short bio

Since 2018 I am an Assistant Professor in the Talgo (Theory, ALgorithms, Graphs, and Optimization) team at the Computer Science Department of École normale supérieure, Paris, France.
Since 2019 I am in the board of the section 6 of the National Committee for Scientific Research For more information, click here.

Before: I have done my PhD with Nicolas Trotignon between 2010 and 2013. I have been a post-doc a Concordia University in Montréal with Vašek Chvátal, in Santiago de Chile at Andres Bello university with José Aliste, in Sophia-Antipolis under the direction of Frédéric Havet, in Université Libre de Bruxelles under the direction of Samuel Fiorini and a I was an ATER in Université Grenoble-Alpes.

Research interests

I am interested in graph theory (non-oriented and oriented), in some problems related to geometry in metric spaces and betweenness. I have also done incursions in combinatorial optimization and distributed algorithms.

In graph theory I am particularly interested in substructures that must apear in a graph or a digraph with particular property. Typical examples: if a graph has large chromatic number, what can you say about its induced subgraphs? Or if a digraph has large minimum outdegree, what can we say about its subgraphs? In geometry, I mainly work on the Chen-Chvátal Conjecture, that proposes a vast generalisation of the geometric de Bruijn-Erdös Theorem.

Published papers

  • Graphs that do not contain a cycle with a node that has at least two neighbors on it
    with M. Radovanovic, N. Trotignon, K. Vuskovic, in SIAM Journal on Discrete Mathematics, 2012.

  • Linear balanceable and subcubic balanceable graphs
    with M. Radovanovic, N. Trotignon, T. Trunck, K. Vuskovic, in Journal of Graph Theory, 2013.

  • Excluding 4-wheels,
    inJournal of Graph Theory, 2014.

  • Number of lines in hypergraphs
    with A. Bondy, X. Chen, E. Chiniforooshan, V. Chvátal, P. Miao, in Journal of Graph Theory, 2014.

  • Excluding cycles with a fixed number of chords
    with N. Bousquet, Discrete Applied Mathematics, 2015.

  • Chen-Chvàtal conjecture for distance hereditary graphs
    with R. Kapadia, European Journal of Combinatorics, 2015.

  • Vertex elimination orderings for hereditary graph classes
    with P. Charbit, N. Trotignon, K. Vušković), in Discrete Mathematics, 2015.

  • Wheel-free planar graphs
    with M. Chudnovsky, P. Seymour and N. Trotignon, in European Journal of Combinatorics, 2015.

  • Excluding clock
    with Z. Li, S. Thomassé, Electronic Notes in Discrete Mathematics, 2015.

  • Lines, metric spaces and betweenness
    with X. Chen, G. Huzhang, R. Kapadia, C. Supko, in Discrete & Computational Geometry, 2016.

  • A new class of graphs that satisfies the Chen-Chv\'atal Conjecture
    with M. Matamala, P. Rochet and J. Zamora, in Journal of Graph Theory, 2016.

  • De Bruijn-Erdos type theorems for graphs and posets
    with G. Lagarde, D. Malec, A. Methuku, C. Tompkins in Discrete Mathematics, 2017.

  • Colouring graphs with constraints on connectivity
    with N. Bretell, F. Havet, N. Trotignon, in Journal of Graph Theore, 2017.

  • Chi-bounded families of oriented graphs
    with J. Bang-Jensen, N. Bousquet, P. Charbit, F. Havet, F. Maffray, J. Zamora, in Journal of Graph Theory, 2018.

  • A tight Erd\H{o}s-P\'osa function for wheel minors (with S. Fiorini, T. Huynh, G. Joret, J.-F. Raymond et I. Sau), SIAM Journal on Discrete Mathematics, 2018.

  • Distributed coloring in sparse graphs with fewer colors
    with M. Bonamy, N. Bousquet, L. Esperet, in PODC 2018 and in Electronic Journal of Combinatorics 2019.

  • Subdivisions in digraphs of large out-degree or large dichromatic number
    with N. Cohen, W. Lochet, F. Havet, P. Mourra, S. Thomassé, in Electronic Journal of Combinatorics, 2019.

  • Extension complexity of the correlation polytop
    with S. Fiorini, T.~Huynh, M.~Macchia, J.~Seif, in Operations Research Letters, 2019.

  • Grundy Coloring & friends, Half-Graphs, Bicliques
    with E. Bonnet, E-J Kim, F. Sikora, STACS 2020.

    Submited papers

  • On the tree-width of even-hole-free graphs
    with I. Adler, E-J Kim, N.L.D. Sintiari and N. Trotignon.

  • Graphs with no induced house nor induced hole have the de Bruijn-Erd\H {o} s property
    with L. Beaudou, M. Matamala, J. Zamora.

  • Extension of Gyarfas-Sumner conjecture to digraphs
    with P. Charbit, R. Naserasr.

  • On the dichromatic number of surfaces.
    with Frédéric Havet, Kolja Knauer, Clément Rambaud.

  • Decomposing and colouring some locally semicomplete digraphs.
    with Guillaume Aubian, Pierre Charbit.


  • On wheel-free graphs, (P. Aboulker, F. Havet, N. Trotignon),



  • 2020-2023, Guillaume Aubian: Coloring Digraphs.

    Stages de M2:

  • 2020 (5 months), Guillaume Aubian (ENS Cachan): Extending Brook's theorem to digraphs.

  • 2021 (5 months), Sarah Houdaigoui (ENS Cachan): Optimization problems in even hole free graphs.

    Stages de L3:

  • 2019, Nina Heloïn (ENS Ulm): around the de Bruijn-Erdos Theorem

  • 2020, Nicolas Daire (ENS Ulm): contraction de graphes

  • 2020, Clément Rambaut (ENS Ulm): dicoloring of graph embedded on surfaces.

  • 2021, Juliette Schabanel (ENS Ulm): dicochromatic number of planar graphs.

  • 2021, Hectore Buffière (ENS Ulm): forced structure in digraphs with large dichromatic number.

  • 2021 (5 months), Gaia Carenini (University School for Advanced Studies, Italia): Chen Chvatal Conjecture.


  • Algorithmique et programmation

  • Initiation à la programmation pour non-informaticiens en Python

  • Graph Minor Theory and its algorithmic consequences. Supports:


  • 2019: 1 week in Leeds visiting Isolde Adler.

  • 2019: 3 weeks in Daejong (South Korea) at the Institute for Basic science.

  • 2019: 3 weeks in Santiago de Chile, at Universidad de Chile, visiting Martin Matamala and jose Zamora.

    Some recent talks

  • Subdivisions in oriented graphs, JGA 2016, November 2016.

  • Subdivisions in oriented graphs, SIWAG, september 2016.

  • Configurations in oriented graphs, Workshop STINT, january 2016.

  • Lines induced by betweenness relations, Conference: Connection in Discrete mathematics, in Simon Fraiser University (Vancouver, Canada), June 2015

  • Excluding clocks, VIII Latin-American Algorithms, Graphs and Optimization Symposium, in Fortaleza, Brasil, Mai 2015.

  • Avancées sur la conjecture de Chen-Chvátal, JGA, Dijon, november 2014.

  • Lines, betweenness and metric spaces, STRUCO, Prague, octber 2014.

  • Avancées sur la conjecture de Chen-Chvátal, séminaire Algorithmique distribuée et Graphes, Paris VII, october 2014.

  • A generalisation of a de Bruijn Erdos Theorem, SIAM Conference on Discrete Math, Minneapolis, United states, june 2014

  • Graphs with no 4-wheels, séminaire Optimisation Combinatoire du G-SCOP (Grenoble), Avril 2012.

  • Around wheel-free graphs, séminaire Graphes et Structures Discrètes, ENS Lyon, Février 2012.

  • Autour des graphes sans roues, séminaire de Combinatoire Algébrique et Géométrique ( Paris 6), Décembre 2011.

  • Les graphes sans roues, JGA, Lyon, Novembre 2011.

    Quelques liens

  • La page personnelle de Nicolas Trotignon mon directeur de thèse.
  • Excellent blog sur la chanson française.