|
|
||
|
IMADA -Department of Mathematics and Computer Science |
|
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 |