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
Miscellaneous
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é.
Manucripts
Excluding slightly more than a cycle (PhD))
On wheel-free graphs,
(P. Aboulker, F. Havet, N. Trotignon),
Encadrements
Post-doc
2022-2023, Raul Wayne Teixeira Lopes
Doctorat:
2020-2023, Guillaume Aubian: Coloring Digraphs.
Stages de M2:
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
Enseignement
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.
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
Mobilité
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)
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
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.
