Article ID Journal Published Year Pages File Type
4952313 Theoretical Computer Science 2017 7 Pages PDF
Abstract
In this paper we study a problem of vertex two-coloring of an undirected graph such that there is no monochromatic cycle of the given length. We show that this problem is hard to solve. We give a proof by presenting a reduction from the variation of satisfiability (SAT) problem. We show the nice properties of coloring cliques with two colors which plays pivotal role in the reduction construction.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,