Les GT se tiennent chaque vendredi de 14h à 15h 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.

Prochains exposés :

Vendredi 17 novembre - Pas de GT cause JGA.

Vendredi 24 novembre 2017 - Homomorphisms of sparse signed graphs - Reza Naserasr (IRIF, Paris).
The notion of homomorphism of graphs has recently been extended to homomorphism of signed graphs in a joint work with E. Rollova and E. Sopena. A key interest in this extension, among many, is that it provides a more intuitive and, at the same time, stronger connection with the notion of minor of (signed) graphs.
In this talk I will present some results from a joint work with C. Charpentier and E. Sopena concerning homomorphisms of sparse signed graphs. Two main results to be mentioned:
Theorem. For any graph G of maximum average degree less than 8/3 and any signature Sigma of G, the signed graph (G,Sigma) maps to (K_4,e). Furthermore, 8/3 is the best possible value here.
As a bipartite analogue of Jaeger-Zhang Conjecture, we propose the following
Conjecture. Every signed bipartite planar graph of unbalanced girth at least 4k-2 maps to the unbalanced cycle of length 2k.
In support of this conjecture, we prove that the claim would hold for signed bipartite planar graphs of unbalanced girth at least 8k.

Vendredi 1er décembre 2017 - Largeur de clique : Majorations polynomiales en termes de largeur arborescente. - Bruno Courcelle (LaBRI).

Dans le cas le plus général, la largeur de clique est exponentielle en la largeur arborescente. Mais pour des classes de graphes "peu denses", notamment celles étudiées par Nesetril et Ossona de Mendez, on a des majorations polynomiales et même souvent linéaires (cas de l'expansion bornée). Mon exposé examine ces majorations. Un algorithme unique (le même pour tous les types de graphes) convertit une décomposition arborescente en terme relatif à la largeur de clique. Les décompositions arborescentes sont fournies sous la forme d'un arbre "normal" analogue à un arbre d'exploration en profondeur.

Mardi 5 décembre 2017 Séminaire commun avec MF - Amphi - La coloration de graphe dans le modèle LOCAL - Partie I - Cyril Gavoille (LaBRI).
L'objectif de cette série d'exposés est de faire découvrir un résultat aussi élégant que surprenant du calcul distribué, à savoir la 3-coloration des n-cycles en temps log*(n). On démontrera l'optimalité de ce résultat ainsi que ces généralisations au cas des graphes arbitraires. Partie I: - Le modèle LOCAL - Le problème de la coloration - Coloration des 1-orientations en 6 couleurs - De 6 à 3 couleurs - Cas des graphes arbitraires

Mardi 12 décembre 2017 Séminaire commun avec MF - Amphi - La coloration de graphe dans le modèle LOCAL - Partie II - Cyril Gavoille (LaBRI).
Partie II: - Coloration rapide des cycles - Borne inférieure en log* sur la coloration des cycles (preuve de Linial) - Une preuve alternative fondé sur le théorème de Ramsey - Etat de l'art

Mardi 19 décembre 2017 - Pique-nique et problèmes ouverts.


Emplois - Stages

Groupe

GT Graphes et Optimisation

Historique

edit SideBar