Short bio
Since 2018, I have been 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 on the board of
Section 6
of the
National Committee for Scientific Research.
For more information, click
here.
Previously, I did my PhD with
Nicolas Trotignon from 2010 to 2013.
I was a postdoctoral researcher at Concordia University in Montréal with
Vašek Chvátal,
at Andres Bello University in Santiago de Chile with
José Aliste,
in Sophia Antipolis under the supervision of
Frédéric Havet,
and at Université Libre de Bruxelles under the supervision of
Samuel Fiorini.
I was also an ATER at 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) and 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? Since a few years, most of my work has focused on the dichromatic number of digraphs, which is a generalisation of the chromatic number of undirected graphs.
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.
On the minimum number of arcs in k-dicritical
oriented graphs with Thomas Bellito, Frédéric Havet and Clément Rambaud. Published in SIAM Journal on Discrete Mathematics, 2024.
(P6, triangle)-free digraphs have bounded dichromatic number
with Guillaume Aubian, Pierre Charbit and Stéphan Thomassé, published in Electronic Journal of Combinatorics, 2024.
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
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.
Computing the degreewidth of a digraph is hard
with Nacim Oijid, Robin Petit, Mathis Rocton, and Christopher-Lloyd Simon.
Blow-ups and extensions of trees in tournaments
with Frédéric Havet, William Lochet, Raul Lopes, Lucas Picasarri-Arrieta, Clément Rambaud.
Induced Disjoint Paths Without an Induced Minor
with Édouard Bonnet, Timothé Picavet, Nicolas Trotignon.
Manucripts
Excluding slightly more than a cycle (PhD))
On wheel-free graphs,
(P. Aboulker, F. Havet, N. Trotignon),
Encadrements
Post-doc
Jan 2025- Dec 2026, Kathryn Nurse
2022-2023, Raul Wayne Teixeira Lopes
Doctorat:
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 M1:
2024 (5 months), Rémy Kimbrough (ENS Ulm): Generalising graph paramaters to digraphs via the backedge graphs.
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): dichromatic 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
Enseignement
Algorithmique et programmation
Initiation à la programmation pour non-informaticiens en Python
Parametrized Complexity. Supports:
Responsabilité Administrative
2025-today: Membre du conseil scientifique du GT graphes
2024-today: Membre du conseil de labo du DI
2022-today: editor for the journal DMTCS, section Graph Theory.
2019-2021: membre du Comité National de la Recherche Scientifique, Section 6.
Grant
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
Mobility
2025: 1 week in Kraków (Poland), visiting Bartosz Walczak (March).
2024: 1 week in Dijon for the JGA (November).
2024: 1 week in Lyon, visiting Nicolas Trotignon (October).
2024: 1 week in Montpellier, visiting Stéphane Bessy (June).
2024: EPIT, school on graph theory in Aussois (May).
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
2024: Maria Chudnovsky (Princeton), Kristina Vuskovic (Leeds), Bogdan Alecu (Leeds) and Nicolas Trotignon (Lyon), 1 week (October)
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
2024 Clique number in tournaments (Slides), in Montpellier, Lyon, Marseille and Kraków.
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.
