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 �8-free and has a dominating set isomorphic to �8, is 2-colorable or not. This algorithm is semi generalization of the 2-colorability algorithm for hypergraph, whose incidence graph is �7-free presented by Camby and Schaudt.

References

[1] Alon N. and Bregman Z., “Every 8-Uniform 8- Regular Hypergraph Is 2-Colorable,” Graphs and Combinatorics, vol. 4, pp. 303-306, 1988.

[2] Beck J., “On 3-Chromatic Hypergraphs,” Discrete Mathematics, vol. 24, no. 2, pp. 127-137, 1978.

[3] Beeri C., Fagin R., Maier D., and Yannakakis M., “On the Desirability of Acyclic Database Schemes,” Journal of the AssoclaUon for Computing Machinery, vol. 30, no. 3, pp. 479-513, 1983.

[4] Bernstein F., Zurtheorie der trigonometrischereihen. Leipz. Ber., vol. 60, pp. 325–328, 1908.

[5] Camby E. and Schaudt O., “A New Characterization of Pk-Free Graphs,” Algorithmica, vol. 75, no. 1, pp. 205-217, 2016.

[6] Erdös P. and Lovász L., “Problems and Results on 3-Chromatic Hypergraphs and Somerelated Questions,” Colloquia Mathematica Societatis Janos Bolyai, vol. 10, pp. 609-627, 1973.

[7] Erdös P., “On A Combinatorial Problem,” Nordisk Matematisk Tidskrift, vol. 11, no. 40, pp. 5-10, 1963.

[8] Garey M. and Johnson D., Computers and Intractability: A Guide to the Theory of NP- completeness, Freeman and Company, 1979.

[9] Henning M. and Yeo A., “2-Colorings in K- Regular K-Uniform Hypergraphs,” European Journal of Combinatorics, vol. 34, no. 7, pp. 1192-1202, 2013.

[10] Linial N. and Tarsi M., “Deciding Hypergraph 2- Colorability by H-resolution,” Theoretical Computer Science, vol. 38, pp. 343-347, 1985.

[11] Lovász L., “Coverings and colorings of hypergraphs,” in Proceedings of 4th Southeastern Conf. on Combinatorics, Graph Theory and Computing, Util. Math. Publ. Congr. Numerantium, VIII, pp. 3-12, 1973.

[12] Radhakrishnan J. and Srinivasan A., “Improved bounds and algorithms for hypergraph 2- coloring,” Random Structures and Algorithms, vol. 16, no. 1, pp. 4-32, 2000.

[13] Szymanska E., “The Complexity of 2-Coloring and Strong Coloring in Uniform Hypergraphs of High Minimum Degree,” Discrete Mathematics and Theoretical Computer Science, vol. 15, no. 2, pp. 121-138, 2013.

[14] van’t Hof P. and Paulusma D., “A New Characterization Of P6-Free Graphs,” Discrete Applied Mathematics, vol. 158, no. 7, pp. 731- 740, 2010.

[15] Vishwanathan S., “Note On 2-Coloring Certain K-Uniform Hypergraphs,” Journal of Combinatorial Theory, Series A, vol. 101, no. 1, pp. 168-172, 2003.

[16] Zhang H., Song L., and Han Z., “Radio Resource Allocation for Device-to-Device Underlay Communication Using Hypergraph Theory,” IEEE Transactions on Wireless Communications, vol. 15, no. 7, pp. 4852-4861, 2016. Ruzayn Quaddoura received his MSc in Theoretical Computer Science from Institute National Polytechnique de Grenoble (INPG, France), and his PhD in Theoretical Computer Science from Picardie Jules Verne University (Amiens, France). Currently he is an assistant professor at Zarqa University, Faculty of Information Technology, Department of Computer Science. His research interests include algorithmic, combinatorial optimization, and graph theory.