Conditions for the Bicolorability of Primitive Hypergraphs
Item
-
Title
Conditions for the Bicolorability of Primitive Hypergraphs
-
Creator
Anthony, Barbara M.
Denman, Richard
-
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.
-
Publisher
The Charles Babbage Research Centre
-
Subject
Primitive hypergraph
Bicolorability
Algorithms