Lucas est chercheur postdoctoral à National Institute of Informatics (NII), Tokyo.
Titre : Edge-colouring and orientations: applications to degree- and χ-boundedness
Bio : As of August 2024, I am a postdoctoral researcher at the National Institute of Informatics (NII) in Tokyo working with Ken-ichi Kawarabayashi. I obtained my PhD (manuscript, slides) in June 2024 at Université Côte D’Azur (Nice), under the supervision of Frédéric Havet and Stéphane Bessy.
My main interests lie in combinatorics and theoretical computer science. In particular, I am interested in graph colouring, directed graphs, reconfiguration, extremal combinatorics and probabilistic methods applied to these areas.
Site web : https://lucaspicasarri.github.io
Résumé : In this talk, we give an extension of Ramsey’s Theorem to edge-coloured graphs, by proving that every 2-edge-coloured graph with large minimum degree contains a monochromatic induced subgraph whose minimum degree remains large.
As a consequence, we deduce that some classes of graphs are degree-bounded. A class C is degree-bounded if, for every integer s, there exists d = d(s) such that every graph G∈C either contains K_{s,s} or has minimum degree at most d. We obtain that the following classes are degree-bounded:
(i) for every k, the graphs G whose edge-set can be k-coloured such that no even hole of G is monochromatic;
(ii) for every fixed antidirected forest F, the graphs admitting an orientation without any induced copy of F;
(iii) for every ℓ≥ 4, the graphs admitting an orientation without any induced antidirected cycle of length at least ℓ.
For k = 2, class (i) contains odd-signable graphs.
Class (ii) characterises the oriented graphs H such that the class of graphs admitting an orientation without any induced copy of H is degree-bounded.
For ℓ= 5, class (iii) contains Burling graphs.
In case (i) and case (iii) for ℓ=4, we further obtain that the classes are polynomially χ-bounded.
Joint work with A. Char and K. Kawarabayashi.
Preprint: https://arxiv.org/pdf/2506.23054