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.

A word about academic publishing
I am convinced that the academic world would greatly benefit from taking its publications out of the hands of private publishers. In combinatorics and particularly in graph theory, we are fortunate to have researchers in the community who have created journals that are entirely free for both authors and readers. Here are 5 examples of excellent journals of this type for graph theory and combinatorics. I encourage everyone to submit their articles to this type of journal.

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 appear 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.
  • Extension complexity of the correlation polytope with S. Fiorini, T.~Huynh, M.~Macchia, J.~Seif, in Operations Research Letters, 2019.
  • 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, 2022.

    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.
  • Heroes in oriented complete multipartite graphs with Guillaume Aubian and Pierre Charbit, in Journal of Graph Theory, 2023.
  • Various bounds on the minimum number of arcs in a $k$-dicritical digraph with Quentin Vermande, Electronic Journal of Combinatorics, 2023.

    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.

    Submited papers

  • On the minimum number of arcs in k-dicritical oriented graphs with Thomas Bellito, Frédéric Havet and Clément Rambaud.
  • (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.
  • Finding forest-orderings of tournaments is NP-complete with Guillaume Aubian and Raul Lopes.
  • Minimum acyclic number and maximum dichromatic number of oriented triangle-free graphs of a given order with Frédéric Havet, François Pirot, Juliette Schabanel.


  • 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 (co-supervised with Pierre Charbit).

    Stages de M2:

  • 2024 (5 months), Samuel Coulomb (ENS Ulm): Clique number of tournaments (co-supervised with Pierre Charbit).
  • 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 Clique Number of tournaments (Slides), IRIF
  • 2023 Colouring digraphs and arc-connectivity (Slides), Clermont-Ferrand
  • 2023 Induced subdigraphs of digraphs with large dichromatic number (Slides), Fortaleza (Brazil)
  • 2022 Induced subgraphs in oriented graphs with large dichromatic number (Slides, Course), School on Graph Theory 2022
  • 2022 Heroes in oriented chordal graphs, ICGT 2022
  • 2021 Analogue of Gyarfas-Sumner conjecture for oriented graphs, ANR Digraphes, 2021
  • 2019 Around the Chen-Chvatal Conjecture, IBS, Daejung, Korea.
  • 2019 Subgraphs of directed graphs with large chromatic number, 9th Slovenian International Conference On Graph Theory.
  • 2016 Subdivisions in oriented graphs, JGA 2016.
  • 2016 Subdivisions in oriented graphs, SIWAG.
  • 2016 Configurations in oriented graphs, Workshop STINT.
  • 2015 Lines induced by betweenness relations, Conference: Connection in Discrete mathematics, in Simon Fraiser University (Vancouver, Canada).
  • 2015 Excluding clocks, VIII Latin-American Algorithms, Graphs and Optimization Symposium, in Fortaleza, Brasil.
  • 2014 Avancées sur la conjecture de Chen-Chvátal, JGA, Dijon.
  • 2014 Lines, betweenness and metric spaces, STRUCO, Prague.
  • 2014 Avancées sur la conjecture de Chen-Chvátal, séminaire Algorithmique distribuée et Graphes, Paris VII.
  • 2014 A generalisation of a de Bruijn Erdős Theorem, SIAM Conference on Discrete Math, Minneapolis, United states.
  • 2012 Graphs with no 4-wheels, séminaire Optimisation Combinatoire du G-SCOP (Grenoble).
  • 2012 Around wheel-free graphs, séminaire Graphes et Structures Discrètes, ENS Lyon.
  • 2011 Autour des graphes sans roues, séminaire de Combinatoire Algébrique et Géométrique ( Paris 6).
  • 2011 Les graphes sans roues, JGA, Lyon.

    Quelques liens

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