Loading Events

« All Events

:

Nicola Lorenz, A Minor Characterisation of Normally Spanned Sets of Vertices

April 8 Tuesday @ 4:30 PM - 5:30 PM KST

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

Speaker

Nicola Lorenz
University of Hamburg

A rooted spanning tree of a graph G is called normal if the endvertices of all edges of G are comparable in the tree order. It is well known that every finite connected graph has a normal spanning tree (also known as depth-first search tree). Also, all countable graphs have normal spanning trees, but uncountable complete graphs for example do not. In 2021, Pitz proved the following characterisation for graphs with normal spanning trees, which had been conjectured by Halin: A connected graph G has a normal spanning tree if and only if every minor of G has countable colouring number, i.e. there is a well-order of the vertices such that every vertex is preceded by only finitely many of its neighbours.

More generally, a not necessarily spanning tree in G is called normal if for every path P in G with both endvertices in T but no inner vertices in T, the endvertices of P are comparable in the tree order. We establish a local version of Pitz’s theorem by characterising for which sets U of vertices of G there is a normal tree in G covering U. The results are joint work with Max Pitz.

Details

Date:
April 8 Tuesday
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:

Venue

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

Organizer

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.