Vertex 2-coloring without monochromatic cycles

Michał Karpiński

In this paper we study a problem of vertex two-coloring of undirected graph such that there is no monochromatic cycle of given length. We show that this problem is hard to solve. W…