BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:e7476707-3edc-42eb-9826-aa3be926c558
X-WR-CALNAME:[soutenance de thèse] - 'Structure de Graphes\, Mineurs et Arb
 res Induits / Structure of Graphs: Minors and Induced Trees' par Claire Hi
 laire
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20250330T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20221030T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20231029T030000
RDATE:20241027T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20230326T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20240331T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:e7476707-3edc-42eb-9826-aa3be926c558
DTSTAMP:20260425T174250Z
CLASS:PUBLIC
DESCRIPTION:[Soutenance en anglais/Talk in english]\n\n\nCette thèse traite
  des questions structurelles de la théorie des graphes qui découlent de mo
 tivations algorithmiques. En effet\, les problèmes de graphes NP-complets 
 sont typiquement plus faciles dès lors qu'on restreint la classe de graphe
 s.\n\nSur les arbres\, qui sont des graphes connexes sans cycles\, la prog
 rammation dynamique donne souvent un algorithme linéaire. Tous les graphes
  ne sont pas des arbres\, mais il est possible de quantifier à quel point 
 un graphe est plus complexe qu'un arbre. Un outil standard pour cela est l
 a largeur arborescente\, qui est profondément liée à la théorie des mineur
 s\, et une autre stratégie consiste à obtenir une structure arborescente e
 n supprimant le moins de sommets possible.\n\nLa première partie de la thè
 se porte sur l'idée de graphes universels pour la relation de mineur. Un g
 raphe est mineur-universel pour une famille de graphes s'il contient comme
  mineur chaque graphe de la famille. Il est en effet plus aisé de manipule
 r un unique graphe plutôt qu’une famille entière pour en déduire des propr
 iétés. De plus\, un résultat célèbre de Robertson\, Seymour et Thomas lie 
 cette notion à la largeur arborescente\, en s’intéressant en particulier a
 u mineur-universel des graphes planaires. Le but est d’étendre leur résult
 at à une famille plus vaste.\n\nLa deuxième partie se concentre sur la rec
 herche d'une grande forêt (union de plusieurs arbres) induite dans un grap
 he. Le théorème d’Erdős-Pósa stipule que si un graphe a peu de cycles disj
 oints\, alors il admet un ensemble de sommets de taille constante dont l'é
 limination produit une forêt. Nous obtenons une propriété similaire pour u
 ne famille plus générale\, la contrepartie de cette généralisation étant q
 ue la taille de cet ensemble est alors logarithmique en la taille du graph
 e\, et cette borne peut être atteinte.\n\n ----------------------------\n
 \nThis thesis deals with structural graph theory questions that stem from 
 algorithmic motivations. Indeed\, NP-complete graph problems are typically
  easier on restricted graph classes. On trees\, which are connected graphs
  without cycles\, dynamic programming often yields a linear algorithm. Not
  every graph is a tree\, but we can measure how much more complex the grap
 h is. A standard tool is the treewidth which is deeply connected to minor 
 theory and another strategy is to obtain a much simpler structure by delet
 ing as few vertices as possible\, as discussed in the second chapter.\n\nT
 he first part of this thesis concerns the idea of minor-universality. A gr
 aph is minor-universal for a family of graphs if it contains as a minor ev
 ery graph in the family. It is indeed easier to deal with a unique graph t
 han the whole family to derive some properties. A celebrated result of Rob
 ertson\, Seymour\, and Thomas links this notion to the minor-universal gra
 ph of planar graphs. Our goal is then to extend their result to wider fami
 lies.\n\nThe second part focuses on finding a large induced forest in a gr
 aph. The Erdős-Pósa theorem states that if a graph does a small number of 
 vertex-disjoint cycles\, then it admits a set of vertices of constant size
  whose removal yields a forest\, called the feedback vertex set. We obtain
  a similar property for a wider graph class\, the trade-off for this gener
 alization being a feedback vertex set whose size depends in the logarithm 
 of the order\, and this is sharp.\n\n\nLe jury sera composé de/The jury wi
 ll be composed of: \n\n- Marthe BONAMY\, PhD Advisor (CR CNRS\, Université
  de Bordeaux) \n- Éric COLIN DE VERDIÈRE\, Examiner (DR CNRS\, Université 
 Gustave Eiffel) \n- David EPPSTEIN Absent reviewer (Distinguished Professo
 r\, University of California) \n- Cyril GAVOILLE\, PhD Advisor (Professeur
 \, Université de Bordeaux) \n- Gwenaël JORET\, Reviewer (Chargé de cours\,
  Université Libre de Bruxelles) \n- Zi-Xia SONG\, Reviewer (Professeure\, 
 University of Central Florida) \n- Marc ZEITOUN\, Examiner (Professeur\, U
 niversité de Bordeaux) \n\n\n[Claire Hilaire] - (Université de Bordeaux\, 
 LaBRI\, France)\nhttps://www.labri.fr/perso/chilaire/
DTSTART;TZID=Europe/Paris:20230704T143000
DTEND;TZID=Europe/Paris:20230704T170000
LOCATION:Amphithéâtre du LaBRI (A30) et https://u-bordeaux-fr.zoom.us/j/845
 56848419
SEQUENCE:0
SUMMARY:[soutenance de thèse] - 'Structure de Graphes\, Mineurs et Arbres I
 nduits / Structure of Graphs: Minors and Induced Trees' par Claire Hilaire
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
