-
Title
-
Conditions for the Bicolorability of Primitive Hypergraphs
-
Creator
-
Anthony, Barbara M.
-
Denman, Richard
-
Date
-
2020-10-16
-
Date Available
-
2020-10-16
-
Date Issued
-
2015-08
-
Identifier
-
Anthony, Barbara & Denman, Richard. (2015). Conditions for the bicolorability of primitive hypergraphs. Journal of Combinatorial Mathematics and Combinatorial Computing. 94. 27-41.
-
uri
-
https://collections.southwestern.edu/s/suscholar/item/251
-
Abstract
-
A primitive hypergraph is a hypergraph with maximum cardinality three and maximum degree three such that every 3-edge is adjacent only to 2-edges and is incident only to vertices of degree two. Deciding the bicolorability of a primitive hypergraph is NP-complete (a straightforward consequence of results in [14]). We provide sufficient conditions, similar to the Sterboul conditions proved by Défossez [5], for the existence of a bicoloring of a primitive hypergraph, and we provide a polynomial algorithm for bicoloring a primitive hypergraph if those conditions hold. We then draw a connection between this algorithm and the well-known necessary and sufficient conditions given by Berge [1] for maximal matchings in graphs, which leads to a characterization of bicolorability of primitive hypergraphs.
-
Language
-
English
-
Publisher
-
The Charles Babbage Research Centre
-
Subject
-
Primitive hypergraph
-
Bicolorability
-
Algorithms
-
Type
-
Article
