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.
From 2019 to 2021 I was 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

Undirected graphs

  • 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, in Journal of Graph Theory, 2014.
  • Excluding cycles with a fixed number of chords with N. Bousquet, in Discrete Applied Mathematics, 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.
  • Colouring graphs with constraints on connectivity with N. Bretell, F. Havet, N. Trotignon, in Journal of Graph Theore, 2017.
  • A tight Erdős-Pósa 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 the Electronic Journal of Combinatorics 2019.
  • Grundy Coloring & friends, Half-Graphs, Bicliques with E. Bonnet, E-J Kim, F. Sikora, STACS 2020.
  • On the tree-width of even-hole-free graphs with I. Adler, E-J Kim, N.L.D. Sintiari and N. Trotignon, in European Journal of Combinatorics, 2021.
  • Vizing's and Shannon's Theorems for defective edge colouring with Guillaume Aubian and Chien-Chung Huang, The Electronic Journal of Combinatorics.

    Directed graphs

  • 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.
  • 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 of Gyarfas-Sumner conjecture to digraphs with P. Charbit, R. Naserasr, in Electronic Journal of Combinatorics (28), 4, 2021.
  • On the dichromatic number of surfaces. with Frédéric Havet, Kolja Knauer, Clément Rambaud, in the Electronic Journal of Combinatorics, 2022.
  • Chordal directed graphs are not directed chi-bounded with Nicolas Bousquet et Rémi de Verclos, in the Electronic Journal of Combinatorics, 2022.
  • Heroes in oriented chordal graphs with Guillaume Aubian and Raphael Steiner, in SIAM J. Discret. Math. 2022
  • Decomposing and colouring some locally semicomplete digraphs with Guillaume Aubian, Pierre Charbit, in European Journal of Combinatorics, 2022
  • Four proofs of the directed Brooks' Theorem with Guillaume Aubian, in Discrete Mathematics, 2022.

    Around the Chen-Chvatal Conjecture

  • Number of lines in hypergraphs with A. Bondy, X. Chen, E. Chiniforooshan, V. Chvátal, P. Miao, in Journal of Graph Theory, 2014.
  • Chen-Chvàtal conjecture for distance hereditary graphs with R. Kapadia, European Journal of Combinatorics, 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-Erdős type theorems for graphs and posets with G. Lagarde, D. Malec, A. Methuku, C. Tompkins, in Discrete Mathematics, 2017.
  • Graphs with no induced house nor induced hole have the de Bruijn-Erdős property with L. Beaudou, M. Matamala, J. Zamora. Published in Journal of Graph Theory, 2022


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

    Submited papers

  • Heroes in oriented complete multipartite graphs with Guillaume Aubian and Pierre Charbit.
  • On the minimum number of arcs in k-dicritical oriented graphs with Thomas Bellito, Frédéric Havet and Clément Rambaud.
  • Various bounds on the minimum number of arcs in a $k$-dicritical digraph with Quentin Vermande.
  • (P6, triangle)-free digraphs have bounded dichromatic number with Guillaume Aubian, Pierre Charbit and Stéphan Thomassé.
  • Digraph Colouring and Arc-Connectivity with Guillaume Aubian and Pierre Charbit.
  • Clique number of tournaments with Guillaume Aubian, Pierre Charbit and Raul Lopes.


  • Excluding slightly more than a cycle (PhD))
  • On wheel-free graphs, (P. Aboulker, F. Havet, N. Trotignon),



  • 2022-2023, Raul Wayne Teixeira Lopes


  • 2020-2023, Guillaume Aubian: Coloring Digraphs.

    Stages de M2:

  • 2024 (5 months), Gaia Carenini (ENS Ulm): Betweenness satisfying the DBE property.
  • 2022 (5 months), Quentin Vermande (ENS Ulm): Minimum number of arcs in k-critical digraphs.
  • 2021 (5 months), Sarah Houdaigoui (ENS Cachan): Optimization problems in even hole free graphs.
  • 2020 (5 months), Guillaume Aubian (ENS Cachan): Extending Brook's theorem to digraphs.

    Stages de L3:

  • 2023 Toan Lopez, CPES: algorithms to dicolour digraphs.
  • 2021 (5 months), Gaia Carenini (University School for Advanced Studies, Italia): Chen Chvatal Conjecture.
  • 2021, Hectore Buffière (ENS Ulm): forced structure in digraphs with large dichromatic number.
  • 2021, Juliette Schabanel (ENS Ulm): dicochromatic number of planar graphs.
  • 2020, Nicolas Daire (ENS Ulm): contraction de graphes
  • 2020, Clément Rambaut (ENS Ulm): dicoloring of graph embedded on surfaces.
  • 2019, Nina Heloïn (ENS Ulm): around the de Bruijn-Erdős Theorem


  • Algorithmique et programmation
  • Initiation à la programmation pour non-informaticiens en Python
  • Parametrized Complexity. Supports:

    Responsabilité Administrative

  • 2022-today: editor for the journal DMTCS, section Graph Theory.
  • 2019-2021: membre du Comité National de la Recherche Scientifique, Section 6.


  • 2021-2024: ANR DAGS and Digraphs Decompositions, 203k euros.
  • 2020-2024: ANR ALGORIDAM, 299k euros.
  • 2019: PI of a PEPS Blanc grant: Erdős-Posa for induced cycle, 10k euros.
  • 2019: PI of an ACI grant: Etude de classe de graphes orientés, 15k euros.

    Committee and organisation

  • 2022: Organisation of JGA 2022
  • 2022: Organisation of the workshop Structures in digraphs at La Maison Clément (20 participants)
  • 2022: PC member of ICGT 2022
  • 2021: Comité de programme des Journée Graphes Algorithmes
  • 2019: invitation to organise a mini symposium at the 9th Slovenian International Conference On Graph Theory


  • 2023: 3 days in Grenoble, visiting Alantha Newman (September).
  • 2023: 1 week in Jena, visiting Bogdan Alecu (August).
  • 2023: 1 week in Sète, 5th ANR digraph meeting (June)
  • 2023: 1 week in Aussois, 1st Workshop on twin-width (May)
  • 2023: 2 weeks in Clermont-Ferrand, visiting Laurent Beaudou (May).
  • 2023: 3 weeks in Fortaleza, visiting Ana Silva (March).
  • 2023: 1 month in Sophia Antipolis, visiting Frédéric Havet (February)
  • 2023: 1 week in Lyon, 4th ANR digraph meeting (January)

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

    They came to visit me

  • 2023: Jose Zamora (Andres Bello University, Chile), 2 week (October)
  • 2023: Maria Chudnovsky (Princeton), Kristina Vuskovic (Leeds), Bogdan Alecu (Leeds) and Nicolas Trotignon (Lyon), 1 week (may)
  • 2023: Alantha Newman (Grenoble), Felix Klingelhöfer (Grenoble) 3 days (June)

    Some recent talks

  • 2023 Colouring digraphs and arc-connectivity (Slides), Clermont-Ferrand
  • 2023 Induced subdigraphs of digraphs with large dichromatic number (Slides), Fortaleza (Brazil)
  • Induced subgraphs in oriented graphs with large dichromatic number (Slides, Course), School on Graph Theory 2022
  • Heroes in oriented chordal graphs, ICGT 2022
  • Analogue of Gyarfas-Sumner conjecture for oriented graphs, ANR Digraphes, 2021
  • Around the Chen-Chvatal Conjecture, IBS, Daejung, Korea, 2019
  • Subgraphs of directed graphs with large chromatic number, 9th Slovenian International Conference On Graph Theory, 2019.
  • 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 Erdős 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.