Bipartiter Graph/Vollständig/2 s/Chromatisches Polynom/Aufgabe/Lösung


Es stehen Farben zur Verfügung, wobei die beiden Teilmengen der bipartiten Zerlegung auf verschiedene Farben Bezug nehmen. Wenn die zweielementige Menge auf nur eine Farbe Bezug nimmt, so gibt es zulässige Färbungen von diesem Typ, da für die -elementige Menge genau Farben zur Verfügung stehen ohne weitere Bedingung. Für die Farbe für haben wir Möglichkeiten, das ergibt insgesamt . Wenn die zweielementige Menge auf zwei Farben Bezug nimmt, so gibt es zulässige Färbungen von diesem Typ. Für die Farben für haben wir Möglichkeiten, was wir mit wegen der beiden möglichen Reihenfolgen multiplizieren müssen. Das ergibt insgesamt .

Insgesamt ist also