(Logo)   IMADA
University of Southern Denmark IMADA -Department of Mathematics and Computer Science
   

COMPUTER SCIENCE COLLOQUIUM

Orientations and connectivity

Florian Hoersch
Instittute of Mathematics
Technische Universitat Ilmenau, Germany

Monday, 29 August, 2022 at 10:15
IMADA's Seminar Room

ABSTRACT

A fundamental theorem of Nash-Williams from 1961 states that a graph has a $k$-arc-connected orientation if and only if it is $2k$-edge-connected. Since then, numerous possibilities of extending this theorem have been considered. Among others, possibilities to impose extra conditions on the orientation in Nash-Williams' theorem, a stronger, more local form of Nash-Williams' theorem and efforts to obtain analagous results for vertex-connectivity will be discussed. I willl describe recent developments, mainly negative complexity results. If time allows, I will show one of the reductions.

Host: Jørgen Bang-Jensen


SDU HOME | IMADA HOME
Daniel Merkle