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. ${\displaystyle {\mathcal {P}}\neq {\mathcal {NP}}}$

See also

• Coloring graphs

Individual evidence

1. ↑ Dorothea Wagner: Theoretical foundations of computer science. (PDF; 874 kB) Preliminary script for the lecture. P. 65 , accessed on February 18, 2012 . 
2. ↑ Dorothea Wagner: Theoretical foundations of computer science. (PDF; 874 kB) Preliminary script for the lecture. P. 82 , accessed February 18, 2012 .