Geodesic
A polynomial time algorithm for checking $2$-chromaticity for recursively constructed $k$-terminal hypergraphs
Trudy Instituta matematiki, Tome 14 (2006) no. 2, pp. 80-85 
V. V. Lepin. A polynomial time algorithm for checking $2$-chromaticity for recursively constructed $k$-terminal hypergraphs. Trudy Instituta matematiki, Tome 14 (2006) no. 2, pp. 80-85. http://geodesic.mathdoc.fr/item/TIMB_2006_14_2_a9/
@article{TIMB_2006_14_2_a9,
     author = {V. V. Lepin},
     title = {A polynomial time algorithm for checking $2$-chromaticity for recursively constructed $k$-terminal hypergraphs},
     journal = {Trudy Instituta matematiki},
     pages = {80--85},
     year = {2006},
     volume = {14},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2006_14_2_a9/}
}
TY  - JOUR
AU  - V. V. Lepin
TI  - A polynomial time algorithm for checking $2$-chromaticity for recursively constructed $k$-terminal hypergraphs
JO  - Trudy Instituta matematiki
PY  - 2006
SP  - 80
EP  - 85
VL  - 14
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMB_2006_14_2_a9/
LA  - ru
ID  - TIMB_2006_14_2_a9
ER  - 
%0 Journal Article
%A V. V. Lepin
%T A polynomial time algorithm for checking $2$-chromaticity for recursively constructed $k$-terminal hypergraphs
%J Trudy Instituta matematiki
%D 2006
%P 80-85
%V 14
%N 2
%U http://geodesic.mathdoc.fr/item/TIMB_2006_14_2_a9/
%G ru
%F TIMB_2006_14_2_a9

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, M., 1982 | MR

[2] Zykov A.A., “Gipergrafy”, UMN, 29:6 (1974), 89–154 | MR | Zbl

[3] Beck J., “An algorithmic approach to the Lovǎsz local lemma”, J. Random Structures and Algorithms, 2:4 (1991), 343–365 | DOI | MR | Zbl

[4] Czumaj A., Scheideler C., “An algorithmic approach to the general Lovǎsz Local Lemma with applications to scheduling and satisfiability problems”, Proc. 32nd STOC, 2000, 38–47 | MR

[5] Czumaj A., Scheideler C., “Coloring non-uniform hypergraphs: A new algorithmic approach to the general Lovǎsz Local Lemma”, Proc. 11th SODA, 2000, 30–39 | MR | Zbl

[6] Erdős P., Lovász L., “Problems and results on 3-chromatic hypergraphs and some related questions”, Infinite and Finite Sets (to Paul Erdǒs on his 60th birthday), v. II, eds. A. Hajnal, R. Rado, and V.T. Sǎs, North-Holland, Amsterdam, 1975, 609–627 | MR

[7] Guruswami V., Hǎstad J., Sudan M., “Hardness of approximate hypergraph coloring”, Proc. 41st FOCS, 2000, 149–158 | MR

[8] Lovász L., “Coverings and colorings of hypergraphs”, Proc. 4th Southeastern Conference on Combinatorics, Graph Theory, and Computing, 1973, 3–12 | MR | Zbl

[9] Lu C-J., “Deterministic hypergraph coloring and its applications”, Proc. 2nd RANDOM, 1998, 35–46 | MR

[10] Radhakrishnan J., Srinivasan A., “Improved bounds and algorithms for hypergraph two-coloring”, Proc. 39th FOCS, 1998, 684–693