On 2-colorability problem for hypergraphs with -free incidence graphs

Abstract EN

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.