The graph formulation of the union-closed sets conjecture - Kölner UniversitätsPublikationsServer

Bruhn, Henning, Charbit, Pierre, Schaudt, Oliver and Telle, Jan Arne (2015). The graph formulation of the union-closed sets conjecture. Eur. J. Comb., 43. S. 210 - 220. LONDON: ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD. ISSN 1095-9971

Full text not available from this repository.

DOI:10.1016/j.ejc.2014.08.030

Abstract

The union-closed sets conjecture asserts that in a finite non-trivial union-closed family of sets there has to be an element that belongs to at least half the sets. We show that this is equivalent to the conjecture that in a finite non-trivial graph there are two adjacent vertices each belonging to at most half of the maximal stable sets. In this graph formulation other special cases become natural. The conjecture is trivially true for non-bipartite graphs and we show that it holds also for the classes of chordal bipartite graphs, subcubic bipartite graphs, bipartite series-parallel graphs and bipartitioned circular interval graphs. We derive that the union-closed sets conjecture holds for all union-closed families being the union-closure of sets of size at most three. (C) 2014 Elsevier Ltd. All rights reserved.

Item Type:

Journal Article

Creators:

Creators	Email	ORCID	ORCID Put Code
Bruhn, Henning	UNSPECIFIED	UNSPECIFIED	UNSPECIFIED
Charbit, Pierre	UNSPECIFIED	UNSPECIFIED	UNSPECIFIED
Schaudt, Oliver	UNSPECIFIED	UNSPECIFIED	UNSPECIFIED
Telle, Jan Arne	UNSPECIFIED	UNSPECIFIED	UNSPECIFIED