TR-2011-06

Sink-stable sets of digraphs

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


Older versions:

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


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