Frédéric MAZOIT
Frédéric Mazoit Maître de Conférences (Université Bordeaux 1)

Équipe LaBRI : Combinatoire et Algorithmique
Page personnelle : http://www.labri.fr/perso/mazoit
Courrier électronique : frederic.mazoitarobaselabri.fr
Bureau : 361
Tél : +33 (0)5 40 00 69 12


Recherche

J'étudie les décompositions de graphes du type des décompositions arborescentes. Ces décompositions et
leurs largeurs associées donnent une idée de la "complexité" d'un graphe donné. Ainsi un grand nombre
de problèmes difficiles comme la coloration peuvent se résoudre dans le cas de graphes de petites
largeurs.

Il existe deux notions de largeur de branches très proches: une pour les graphes et une pour les
matroïdes. Or, à chaque graphe correspond un matroïde. Il est donc naturel de se demander si la largeur
de branches d'un graphe est toujours égale à celle de son matroïde. De nombreaux auteurs dont
Robertson, Thomas ou encore Geelen ont posé cette question. Avec Stéphan Thomassé du LIRMM, avons
montré que sauf pour les arbres, ces deux largeurs sont égales.

Il existe dans la littérature un grand nombre de variantes de décompositions de graphes (arborescentes,
en chemins, en branches...). Beaucoup d'entre-elles admettent un théorème d'obstruction du type:" pour
tout entier k, il existe une décomposition de largeur k si et seulement si il n'existe pas
d''enchevêtrement' d'ordre k " avec, à chaque fois, une preuve ad-hoc. Avec Omid, Amini de l'ENS,
Nicolas Nisse de l'INRIA Sophia-Antipolis et Stéphan Thomassé, nous avons défini un cadre très général
dans lequel nous avons montré un unique théorème de ce type qui généralise et unifie tous les théorèmes
d'obstruction connus à ce jour. Dans un second temps, avec Laurent Lyaudet du LIFO et Stéphan Thomassé,
nous avons réussi à beaucoup la simplifier le coeur de la preuve.

À tout graphe G plongé dans une surface S de genre g correspond un graphe dual G* obtenu en choisissant
un sommet par face et en prenant, pour chaque arête e de G, une arête e* reliant les deux faces bordant
e. Comme il est très facile de construire G* à partir de G, il est naturel d'imaginer que G* et G ont
une "complexité" similaire. J'ai ainsi montré que la différence entre la largeur arborescente de G et
celle de G* est au plus 1+g.

Extrait de publications









Administration

Depuis 2009, je suis webmestre du site du département d'informatique

Comité de programme & Comité d'organisation

J'ai fait parti du comité d'organisation de STACS en 2006 et 2008 et d'ICALP en 2010

Diffusion

J'ai publié deux articles de vulgarisation.
2009 Sur un théorème de pavage d'un rectangle, Bulletin vert de l'APMEP, n°480 pages 113-118, 2009.
2006 Pavages par des calissons, feuille à problèmes n°4 de l'IREM de Lyon, 2006.

Page mise à jour le 13/08/2010 à 10:56