## Amadeus Reinald gave a talk on the twin-width of graphs of girth at least 5 without an induced subdivision of $K_{2,3}$ at the Discrete Math Seminar

On June 13, 2022, Amadeus Reinald from the ENS de Lyon and the IBS Discrete Mathematics Group gave a talk at the Discrete Math Seminar, proving that graphs of girth at least 5 without an induced subdivision of $K_{2,3}$ have bounded twin-width. The title of his talk was “Twin-width and forbidden subdivisions“.

## Amadeus Reinald, Twin-width and forbidden subdivisions

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.

## Welcome Amadeus Reinald, a visiting graduate student in the IBS Discrete Mathematics Group from the ENS de Lyon

The IBS Discrete Mathematics Group welcomes Amadeus Reinald, a visiting graduate student from the ENS de Lyon in France. He is planning to stay with us until August 26, 2022.

기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 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