Romain Bourneuf

About me

I am a first year PhD student at LaBRI (Bordeaux) and ENS de Lyon, with Marthe Bonamy and Stéphan Thomassé.

Interests

My main interests lie in structural and algorithmic graph theory.

Personal Info

  • Email: romain.bourneuf(at)ens-lyon.fr
  • My CV: (PDF)

Academic background

Internships

February 2024 - July 2024

5 months internship with Marcin Pilipczuk at University of Warsaw, Poland.

I am studying various structural and algorithmic properties of hereditary graph classes.


September 2023 - February 2024

5 months internship with Johannes Carmesin at University of Birmingham, UK.

I studied the algorithmic aspects of decomposing a graph into 4-connected components.


February 2023 - July 2023

6 months internship with Stéphan Thomassé at ENS de Lyon, France.

The aim of this internship was to study the χ-boundedness of graphs of bounded twin-width. I also studied other problems related to structures of bounded twin-width. You can find here my master's thesis and the slides of my defense.


Summer 2022

4 months internship with Alon Rosen at Bocconi University, Milano, Italy.

During this internship, I studied the complexity of various total search problems related to extremal combinatorics.


Summer 2021

6 weeks internship with Marthe Bonamy at LaBRI, Bordeaux, France.

This internship was my first experience with graph theory. I studied Brandes' algorithm to compute the betweenness centrality in a graph.

Education

2021 - 2023

Master's degree at ENS de Lyon.

I studied various topics, including graph theory, combinatorics, algebra, cryptography and complexity.


2020 - 2021

Licence's degree at ENS de Lyon.

I studied fundamental computer science and mathematics.


2018 - 2020

Scientific Preparatory Class at Lycée Chateaubriand, Rennes.

Two years studying mathematics, computer science and physics in order to join the ENS.

Publications

Preprints

A tamed family of triangle-free graphs with unbounded chromatic number. With Édouard Bonnet, Julien Duron, Colin Geniet, Stéphan Thomassé, Nicolas Trotignon. (See on Arxiv)

Bounded twin-width graphs are polynomially χ-bounded. With Stéphan Thomassé. (See on Arxiv)

Conferences

Bounding ε-scatter dimension via metric sparsity. With Marcin Pilipczuk, SODA 2025. (See on Arxiv)

Factoring Pattern-Free Permutations into Separable ones. With Édouard Bonnet, Colin Geniet, Stéphan Thomassé, SODA 2024. (See on Arxiv)

PPP-Completeness and Extremal Combinatorics. With Lukáš Folwarczný, Pavel Hubáček, Alon Rosen, Nikolaj Ignatieff Schwartzbach, ITCS 2023. (See on Arxiv)

Journals

On polynomial degree-boundedness. With Matija Bucić, Linda Cook, James Davies. In Advances in Combinatorics (See also on Arxiv)

Conferences & Events

Conferences

Innovations in Theoretical Computer Science, ITCS 2023, MIT. PPP-Completeness and Extremal Combinatorics. (Slides)

Events as a speaker

Team Seminar, LaBRI, Bordeaux, 2024. A tamed family of triangle-free graphs with unbounded chromatic number. (Slides)

3rd Workshop on Complexity and Algorithms, CoA 2023, Paris. PPP-Completeness and Extremal Combinatorics. (Slides)

FPT Fest in the honour of Mike Fellows, Bergen, 2023. Bounded twin-width graphs are polynomially χ-bounded. (Slides)

1st Workshop on Twin-Width, Aussois, 2023. Bounded twin-width graphs are polynomially χ-bounded. (Slides)

Events as a non-speaker

Structural Graph Theory Workshop 2, Chęciny, 2024.

EPIT - Graphs and Algorithms: Conjectures, Aussois, 2024.

Sparse Graphs Coalition 2024 Session 1, Online, 2024.

Structural Graph Theory Workshop, Bȩdlewo, 2023.

Structural Graph Theory Bootcamp, Warsaw, 2023.

Digraphs meeting, Sète, 2023.

Milan Theory Workshop, Bocconi, 2022.

Teaching

Club de mathématiques discrètes