14:00
15:00

/Exposé en anglais/Talk in english/

Tree decompositions are a powerful tool in structural graph theory; they are traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has until recently remained out of reach. Tree decompositions are closely related to the existence of "laminar collections of separations" in a graph, which roughly means that the separations in the collection "cooperate" with each other, and the pieces that are obtained when the graph is simultaneously decomposed by all the separations in the collection "line up" to form a tree structure. Such collections of separations come up naturally in the context of forbidden minors. In the case of families where induced subgraphs are excluded, while there are often natural separations, they are usually very far from forming a laminar collection. However, under certain circumstances, these collections of natural separations can be partitioned into a number of laminar collections, and the number of laminar collections needed is logarithmic in the number of vertices of the graph. This in turn allows us to obtain a wide variety of structural and algorithmic results, which we will discuss in this talk.

[Maria Chudnovsky] (Princeton University)

http://web.math.princeton.edu/~mchudnov/

{Remarques/Remarks}


Cet exposé sera enregistré, merci de désactiver votre webcam et micro si vous ne souhaitez pas apparaître sur l'enregistrement. Les échanges informels avant et après l'exposé, ainsi que les questions, ne seront pas enregistrés.

N'hésitez pas à venir un peu avant le début de l'exposé pour faire des tests (et discuter informellement). Nous auront également des discussions informelles post-GT.

À très bientôt,

Claire, Marthe & Jonathan

Retrouvez toutes les informations du GT dématérialisé sur https://combalgo.labri.fr/pmwiki.php/Groupe/GT-en-LIGNE


This presentation will be recorded, please deactivate your webcam and microphone if you do not wish to appear on the recording. Informal exchanges before and after the presentation, as well as questions, will not be recorded.

Do not hesitate to come a little before the start of the presentation to test (and chat informally). We will also have informal post-working group discussions.

See you soon,

Claire, Marthe & Jonathan

Find all the information of the dematerialized working group on the web page https://combalgo.labri.fr/pmwiki.php/Groupe/GT-en-LIGNE

A30/178 et sur https://u-bordeaux-fr.zoom.us/j/4939941120