Three color problem
The three-color problem is a decision problem from graph theory . The question is whether the nodes of a simple graph can be colored with three colors so that adjacent nodes have different colors. The problem is NP-complete .
One generalization is the coloring problem. A variant known as the map coloring problem is also known.
For 3COLOR there cannot be a relative approximation algorithm with a quality guarantee of 4/3 or better, if . From this it follows that there can be no polynomial approximation scheme and no absolute approximation algorithm for COLOR.
See also
Individual evidence
- ↑ Dorothea Wagner: Theoretical foundations of computer science. (PDF; 874 kB) Preliminary script for the lecture. P. 65 , accessed on February 18, 2012 .
- ↑ Dorothea Wagner: Theoretical foundations of computer science. (PDF; 874 kB) Preliminary script for the lecture. P. 82 , accessed February 18, 2012 .