On 2-Colorability Problem for Hypergraphs with -free Incidence Graphs

Ruzayn Quaddoura

Faculty of Information Technology, Zarqa University, Jordan

Abstract: A 2-coloring of a hypergraph is a mapping from its vertex set to a set of two colors such that no edge is monochromatic. The hypergraph 2- Coloring Problem is the question whether a given hypergraph is 2-colorable. It is known that deciding the 2-colorability of hypergraphs is NP-complete even for hypergraphs whose hyperedges have size at most 3. In this paper, we present a polynomial time algorithm for deciding if a hypergraph, whose incidence graph is -free and has a dominating set isomorphic to , is 2-colorable or not. This algorithm is semi generalization of the 2-colorability algorithm for hypergraph, whose incidence graph is -free presented by Camby and Schaudt.

Keywords: Hypergraph, Dominating set, -free graph, Computational Complexity.

Received December 17, 2018; accepted June 11, 2019
https://doi.org/10.34028/iajit/17/2/14

Full text