Sink-stable sets of digraphs (Revised version)

Dóra Erdős, András Frank, Krisztián Kun


We introduce the notion of sink-stable sets of a digraph and prove a min-max formula for the maximum cardinality of the union of $k$ sink-stable sets. The results imply a recent min-max theorem of Abeledo and Atkinson on the Clar number of bipartite plane graphs and a sharpening of Minty's coloring theorem. We also exhibit a link to min-max results of Bessy and Thomassé and of Sebő on cyclic stable sets.

Previous version can be found here.

Bibtex entry:

AUTHOR = {Erd{\H o}s, D{\'o}ra and Frank, Andr{\'a}s and Kun, Kriszti{\'a}n},
TITLE = {Sink-stable sets of digraphs (Revised version)},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2011},
NUMBER = {TR-2011-06}

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