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 Sebo on cyclic stable sets.
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}, |
NOTE | = | {{\tt egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2011}, |
NUMBER | = | {TR-2011-06} |