Ein knotengefärbter Graph ist in der Graphentheorie ein Graph, dessen Knoten Farben zugeordnet werden.

Formal wird die Farbe durch ein Element einer beliebigen diskreten Menge angegeben. Sie kann zum Beispiel einer natürlichen Zahl entsprechen (es kommt dabei in der Regel nicht auf den Wert der Zahl an, sondern auf die Unterscheidbarkeit der Zahlen voneinander).

Die Färbung eines knotengefärbten Graphen ist dann eine Funktion, die von den Knoten in die Menge der Farben abbildet.

Literatur

• Reinhard Diestel: Graphentheorie. 3. Auflage. Springer, 2006, ISBN 3-540-21391-0 (online).