Groupe

GT

Les GT se tiennent chaque vendredi de 14h à 15h (d'ordinaire en salle 178). Vous êtes invités à venir 10 minutes avant pour partager thé, café et gâteaux.

Pour vous inscrire à la liste de diffusion, il suffit d'envoyer un mail à sympa@diff.u-bordeaux.fr avec pour sujet "subscribe labri.go-gt Cookie Monster", où Cookie est remplacé par votre prénom et Monster par votre nom.

Voir l'agenda des GT : https://webmel.u-bordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.go.html; pour l'ajouter au vôtre, https://webmel.u-bordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.go.ics ou bien flasher le QRCode suivant:

Les exposés en ligne sont accessibles à cette adresse : https://webconf.u-bordeaux.fr/b/mar-ef4-zed.

Prochains exposés :

Vendredi 06 Fevrier Double GT

14h00 - Benjamin Duhamel
Excluding a Forest Induced Minor

In the first paper of the Graph Minors series [JCTB ’83], Robertson and Seymour proved the Forest Minor theorem: the H-minor-free graphs have bounded pathwidth if and only if H is a forest. In recent years, considerable effort has been devoted to understanding the unavoidable induced substructures of graphs with large pathwidth or large treewidth. In this paper, we give an induced counterpart of the Forest Minor theorem: for any t ⩾ 2, the Kt,t-subgraph-free H-induced-minor-free graphs have bounded pathwidth if and only if H belongs to a class F of forests, which we describe as the induced minors of two (very similar) infinite parameterized families. This constitutes a significant step toward classifying the graphs H for which every weakly sparse H-induced-minor-free class has bounded treewidth. Our work builds on the theory of constellations developed in the Induced Subgraphs and Tree Decompositions series.
This is joint work with Édouard Bonnet and Robert Hickingbotham.

14h45 - Oscar Fontaine
On the size of k-irreducible triangulations

A triangulation of a surface is k-irreducible if every edge belongs to a non-contractible curve of length k and there are no shorter non-contractible curves. We prove that a k-irreducible triangulation of an orientable surface of genus g has O(k^2g) triangles, which is optimal. This is a factorial improvement in k and a quadratic improvement in g over the previous best bound due to Gao, Richter and Seymour. This is a joined work with Vincent Delecroix and Arnaud de Mesmay.

Emplois - Stages

Groupe

GT Graphes et Optimisation

Historique

edit SideBar

Blix theme adapted by David Gilbert, powered by PmWiki