Bonjour à tous,

Le prochain séminaire Graphes@Lyon aura lieu le vendredi 10 novembre à 10h au LIRIS en salle C1 du Nautibus. Nous aurons le plaisir d’écouter Lucas Pastor, doctorant au G-scop (Grenoble).

Titre : Colouring squares of claw-free graphs

Résumé : Let G be a claw-free graph.  We consider the square G^2 of G, which is the
graph formed from G by the addition of edges between those pairs of vertices
connected by some two-edge path in G, and consider proper colourings of G^2. In
particular, we relate the chromatic number of G^2 to the clique number of G.
We prove that there is an absolute constant epsilon > 0 such that the chromatic
number of G^2 is at most (2- epsilon)χ(G)^2 for any claw-free graph G. Our main
theorem extends a result of Molloy and Reed who first gave a positive answer to
a conjecture of Erdős and Nešetřil.

Joint-work with Rémi de Joannis de Verclos and Ross Kang.

En espérant vous voir nombreux !

Aline Parreau