Conditions for the Bicolorability of Primitive Hypergraphs

Item

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