# O-joung Kwon (권오정), Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)

## January 25 Tuesday @ 4:30 PM - 5:30 PM KST

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

### Speaker

O-joung Kwon (권오정)
Incheon National University & IBS Discrete Mathematics Group
http://ojkwon.com

In a reduction sequence of a graph, vertices are successively identified until the graph has one vertex. At each step, when identifying $u$ and $v$, each edge incident to exactly one of $u$ and $v$ is coloured red. Bonnet, Kim, Thomassé, and Watrigant [FOCS 2020] defined the twin-width of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has maximum degree at most $k$. For any graph parameter $f$, we define the reduced-$f$ of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has $f$ at most $k$. Our focus is on graph classes with bounded reduced-bandwidth, which implies and is stronger than bounded twin-width (reduced-maximum-degree).

We show that every proper minor-closed class has bounded reduced-bandwidth, which is qualitatively stronger than a result of Bonnet et al. for bounded twin-width. In many instances, we also make quantitative improvements. For example, all previous upper bounds on the twin-width of planar graphs were at least $2^{1000}$. We show that planar graphs have reduced-bandwidth at most $466$ and twin-width at most $583$; moreover, the witnessing reduction sequence can be constructed in polynomial time. We show that $d$-powers of graphs in a proper minor-closed class have bounded reduced-bandwidth (irrespective of the degree of the vertices).

This is joint work with Édouard bonnet and David Wood.

## Details

Date:
January 25 Tuesday
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:
,
`

Room B232
IBS (기초과학연구원)

## Organizer

Sang-il Oum (엄상일)
View Organizer Website
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 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