TR-2011-06

Sink-stable sets of digraphs (Revised version)

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



Abstract

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:

@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}
}


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