Loading Events

« All Events

  • This event has passed.

Amadeus Reinald, Twin-width and forbidden subdivisions

June 13 Monday @ 4:30 PM - 5:30 PM KST

Room B332, IBS (기초과학연구원)


Amadeus Reinald
ENS de Lyon & IBS Discrete Mathematics Group

Twin-width is a recently introduced graph parameter based on vertex contraction sequences. On classes of bounded twin-width, problems expressible in FO logic can be solved in FPT time when provided with a sequence witnessing the bound. Classes of bounded twin-width are very diverse, notably including bounded rank-width, $\Omega ( \log (n) )$-subdivisions of graphs of size $n$, and proper minor closed classes. In this talk, we look at developing a structural understanding of twin-width in terms of induced subdivisions.

Structural characterizations of graph parameters have mostly looked at graph minors, for instance, bounded tree-width graphs are exactly those forbidding a large wall minor. An analogue in terms of induced subgraphs could be that, for sparse graphs, large treewidth implies the existence of an induced subdivision of a large wall. However, Sintiari and Trotignon have ruled out such a characterization by showing the existence of graphs with arbitrarily large girth avoiding any induced subdivision of a theta ($K_{2,3}$). Abrishami, Chudnovsky, Hajebi and Spirkl have recently shown that such (theta, triangle)-free classes have nevertheless logarithmic treewidth.

After an introduction to twin-width and its ties to vertex orderings, we show that theta-free graphs of girth at least 5 have bounded twin-width.

Joint work with Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé and Rémi Watrigant.


June 13 Monday
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:


Room B332
IBS (기초과학연구원)
+ Google Map


Sang-il Oum (엄상일)
View Organizer Website
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.