TR-2011-06

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 Sebo on cyclic stable sets.
 

Previous version can be found here.

Bibtex entry:

@techreport{egres-11-06,

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 www.cs.elte.hu/egres}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2011},
NUMBER	=	{TR-2011-06}

}