Can I read Vertex 2-Coloring Without Monochromatic Cycles on EtoBox?

Vertex 2-Coloring Without Monochromatic Cycles by Karpiński, Michał is a scholarly article available to read on EtoBox.

What is Vertex 2-Coloring Without Monochromatic Cycles about?

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. We give a proof by presenting a reduction from variation of satisfiability (SAT) problem. We show nice properties of coloring cliques with two colors which plays pivotal role in the reduction construction.

Author

Karpiński, Michał

Published

2014

Language

EN