Packing directed circuits

B. Reed, N. Robertson, P. Seymour, R.THOMAS

IBP-EC 1995/11: Rapport de Recherche EC / EC research reports
29 pages - Janvier/January 1996 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Packing directed circuits

Résumé : On démontre la conjecture suivante de Younger : Pour chaque entier n , il existe un autre entier t tel que pour tout graphe orienté D , soit il existe n circuits sommets disjoints, soit il existe un ensemble X de sommets de cardinalité au plus t tel que D-X est acyclique.

Abstract : We prove a conjecture of Younger, that for every integer n „ 0 there exists an integer t „ 0 such that for every digraph G , either G has n vertex-disjoint directed circuits, or G can be made acyclic by deleting at most t vertices.

Publications internes EC 1995 / EC research reports 1995