On factorizations of directed graphs by cycles

Gyula Pap, László Szegő


In this paper we present a min-max theorem for a factorization problem in directed graphs. This extends the Berge-Tutte formula on matchings as well as formulas for the maximum even factor in weakly symmetric directed graphs and a factorization problem in undirected graphs. We also prove an extension to the structural theorem of Gallai and Edmonds about a canonical set attaining minimum in the formula. The matching matroid can be generalized to this context: we get a matroidal description of the coverable node sets.

Bibtex entry:

AUTHOR = {Pap, Gyula and Szeg{\H o}, L{\'a}szl{\'o}},
TITLE = {On factorizations of directed graphs by cycles},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2004},
NUMBER = {TR-2004-01}

Last modification: 29.12.2020. Please email your comments to Tamás Király!