Orientations of infinite graphs

Graphs, Hypergraphs, and Computing

27 February 15:30 - 16:30

Carsten Thomassen - Technical University of Denmark, DTU

In 1960 Nash-Williams proved that every 2k-edge-connected finite graph has a k-arc-connected orientation. More precisely, every edge can be given a direction such that every cut has at least k arcs (directed edges) in each direction.

In 1989 I conjectured that the same result holds for infinite graphs if we replace the edge-connectivity 2k by a larger edge-connectivity f(k). In this talk I will discuss the recent proof of this conjecture.

The weaker version of Nash-Williams' theorem that every 4k-edge-connected finite graph has a k-arc-connected orientation follows immediately from the theorem of Tutte and Nash-Williams from 1961 (and generalized to matroids by Edmonds in 1965) that every 4k-edge-connected finite graphs has 2k pairwise edge-disjoint spanning trees. But this does not extend to infinite graphs. Indeed, there is no finite edge-connectivity guaranteeing an infinite graph to have two edge-disjoint spanning trees, as proved in 1989 by Aharoni and myself.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to