3COLOR

Das Dreifarbenproblem ist ein Entscheidungsproblem aus der Graphentheorie. Gefragt ist, ob die Knoten eines schlichten Graphen so mit drei Farben einfärbbar sind, dass zueinander benachbarte Knoten unterschiedliche Farben haben. Das Problem ist NP-vollständig.

Eine Verallgemeinerung ist das Färbungsproblem. Bekannt ist auch eine als Landkartenfärbungsproblem bekannte Variante.

Siehe auch


Wikimedia Foundation.

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”