Graph/Färbung/Homomorphismus/Aufgabe/Kommentar

Eine zulässige Färbung ${}f\colon G\rightarrow B$ ist nichts anderes als eine Abbildung, so dass ${}f(u)\neq f(v)$ ist, wenn ${}u$ und ${}v$ benachbart sind. Dies bedeutet, dass ${}\{f(u),f(v)\}$ eine Kante des vollständigen Graphen ${}(B,{\mathfrak {P}}_{2}\,(B))$ ist, wenn ${}\{u,v\}$ eine Kante von ${}G$ ist, d.h. ${}f\colon G\rightarrow (B,{\mathfrak {P}}_{2}\,(B))$ ist ein Graphhomomorphismus.

Diese Aufgabe besagt, dass man stattdessen Graphhomomorphismen untersuchen kann, um zulässige Färbungen von Graphen zu untersuchen. Siehe dazu Aufgabe und

Aufgabe.

Zur kommentierten Aufgabe