Färbung (Graphentheorie)

Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. Eine Verallgemeinerung ist der Begriff der Listenfärbung, d. i. die Zuordnung von „Listen“ verfügbarer Farben, wobei der Graph nun eine gültige Färbung aus diesen Listen erhalten soll. Des Weiteren gibt es die Totalfärbung, die sowohl Kantenfärbung als auch Knotenfärbung umfasst.

In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder „gültigen“ Färbungen (siehe unten), und versucht, Algorithmen zu entwickeln, die für einen vorgegebenen Graphen eine gültige Färbung mit möglichst wenigen Farben finden. Probleme aus der diskreten Mathematik, aber auch außermathematische Fragestellungen lassen sich manchmal in ein Färbungsproblem übersetzen, daher ist die Existenz oder Nichtexistenz solcher Algorithmen auch außerhalb der Graphentheorie von Interesse.