DSpace Repository

Conditions for the Bicolorability of Primitive Hypergraphs

Show simple item record

dc.contributor.author Anthony, Barbara M.
dc.contributor.author Denman, Richard
dc.date.accessioned 2020-10-16T14:22:25Z
dc.date.available 2020-10-16T14:22:25Z
dc.date.issued 2015-08
dc.identifier.citation Anthony, Barbara & Denman, Richard. (2015). Conditions for the bicolorability of primitive hypergraphs. Journal of Combinatorial Mathematics and Combinatorial Computing. 94. 27-41. en_US
dc.identifier.uri http://hdl.handle.net/11214/239
dc.description.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. en_US
dc.language.iso en_US en_US
dc.publisher The Charles Babbage Research Centre en_US
dc.subject Primitive hypergraph en_US
dc.subject Bicolorability en_US
dc.subject Algorithms en_US
dc.title Conditions for the Bicolorability of Primitive Hypergraphs en_US
dc.type Article en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search


Browse

My Account

Links