Loading Events

« All Events

  • This event has passed.
:

Maria Chudnovsky, Induced subgraphs and tree decompositions

Wednesday, July 28, 2021 @ 3:00 PM - 4:00 PM KST

Zoom ID: 869 4632 6610 (ibsdimag)

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. In what follows we mostly focus on families of graphs of bounded degree. It turns out that due to the bound on the degree, these collections of natural separations can be partitioned into a bounded number of laminar collections. This in turn allows to us obtain a wide variety of structural and algorithmic results, which we will survey in this talk.

Details

Date:
Wednesday, July 28, 2021
Time:
3:00 PM - 4:00 PM KST
Event Category:
Event Tags:

Venue

Zoom ID: 869 4632 6610 (ibsdimag)

Organizer

O-joung Kwon (권오정)
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.