A polynomial time algorithm for checking $2$-chromaticity for recursively constructed $k$-terminal hypergraphs

V. V. Lepin

Institute of Mathematics of the National Academy of Sciences of Belarus

Abstract: It is shown that for $k$-terminal recursively constructed hypergraphs the $2$-colorability problem: for a given hypergraph $H$ to find out whether there exists a coloring $f\colon V(H)\to\{1,2\}$ such that no edge of $H$ is monochromatic, can be solved in $O(n^3)$ time.

UDC: 519.1

Received: 30.12.2005