Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952313 | Theoretical Computer Science | 2017 | 7 Pages |
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
MichaÅ KarpiÅski,