Paths and circuits in strongly connected oriented graphs.

Stéphan Thomassé Laboratoire LaPCS, Lyon

One of the more general extension of Dilworth’s theorem: ”The size of a maximum antichain of a poset P equals the smallest number of chain which partition P ” is Gallai-Milgram’s result: ”The size of a maximum stable set of a digraph D (denoted by α) is not less than the smallest number of paths which partition D”. Our goal in this talk is to present two extensions of Gallai-Milgram’s theorem to strongly connected digraphs. We will mainly focus on two conjectures:

Conjecture 1 (Gallai ’64) Every strongly connected digraph D can be spanned by the union of α circuits.

Conjecture 2 (Las Vergnas ’83) Every strongly connected digraph D can be partitioned into (α − 1) paths, provided that α > 1.

The case α = 1 in Conjecture 1 is a well-known theorem of Camion, and the proof for α = 2 was given by Chen and Manalastasn, and then simplified by Bondy. We will sketch the proof of the case α = 3 of Gallai’s conjecture. We will also link this question to the (NP-hard) problem of determining a minimal spanning strongly connected subgraph. In the second part of the talk, a proof of Las-Vergnas’ conjecture will be presented.