Wie lautet das chromatische Polynom des vollständig bipartiten Graphen?
Meine Idee:
Die Knotenmenge besteht ja aus 2 disjunkten Teilmengen mit Mächtigkeit m bzw. n.
Jeden Knoten aus einer Menge, hier m, kann man mit allen Farben färben, da die nicht untereinander verbunden sind.
Jeder Knoten aus der anderen Menge darf dann diese m Farben nicht mehr haben und das auch für jeden Knoten n.
Ist das so richtig?
Danke
2 Antworten
Hm.
Zu einer gegebenen Zahl λ gibt das chromatische Polynom ja an, wieviele Färbungen des Graphen es mit λ Farben gibt. Das heißt insbesondere, dass für alle solche Zahlen der Wert des Polynoms an dieser Stelle eine nicht-negative Zahl ist. Und außerdem weißt du, dass der Wert an der Stelle λ=2 auf jeden Fall sogar echt größer als Null sein muss.
Für m=2 sagt aber dein Polynom, dass es KEINE Färbung gibt. Wenn m größer ist als λ und n ungerade, dann kommt als Wert sogar eine negative Zahl heraus.
Konkret: Nach deiner Formel gibt es z. B. für K_(4,3) und λ=3 Farben gerade
P(4) = 3^4 * (3-4)³ = 81 * (-1) = -81 Färbungen.
Nein, das kann so nicht stimmen.
Du gehst davon aus, dass im ersten Schritt m Farben verwendet werden und diese daher im zweiten Schritt nicht mehr verwendet werden dürfen. Warum soll das so sein? Ich kann ja die m Knoten der einen Partition auch mit genau einer Farbe färben, dann habe ich für die zweite Partition nicht mehr nur λ−m , sondern sogar λ−1 Farben zur Verfügung.
Wenn alle Knoten in m dieselbe Farben haben gibt es für λ Farben:
λ*(λ-1)^n Möglichkeiten
Wenn ein Knoten in m eine andere Farbe hat:
.. und da hörts dann schon auf
Die m Knoten in der ersten Menge sind nicht miteinander verbunden, heißt, sie können unabhängig voneinander gefärbt werden. Es gibt λ Möglichkeiten, jeden dieser Knoten zu färben, also λm Möglichkeiten für die erste Menge.
Die n Knoten in der zweiten Menge sind mit allen m Knoten der ersten Menge verbunden. Das bedeutet, jeder dieser nKnoten darf keine der mFarben verwenden, die bereits in der ersten Menge verwendet wurden. Es bleiben also λ−m Farben für jeden der nKnoten übrig. Es gibt somit (λ−m)^n Möglichkeiten, die zweite Menge zu färben.
Die Gesamtzahl der Färbungen ergibt sich aus der Kombination der Möglichkeiten für beide Mengen: Die Gesamtzahl der Färbungen ergibt sich aus der Kombination der Möglichkeiten für beide Mengen:
Also: ist ein flauschiges Ergebnis! xD
Die m Knoten in der ersten Menge sind nicht miteinander verbunden, heißt, sie können unabhängig voneinander gefärbt werden. Es gibt λ Möglichkeiten, jeden dieser Knoten zu färben, also λm Möglichkeiten für die erste Menge.
Das wäre dann ja aber λ^m Möglichkeiten und nicht λm.
Und wenn ich deine Lösung diesbezüglich korrigiere, dann ist es die gleich, wie ich habe.
Danke, ja ich verstehe die Problematik. Man müsste wohl eine Fallunterscheidung machen für die Anzahl der verwendeten Farben, dafür dann das chromatische Polynom aufstellen und am Ende alles addieren.
Das wirkt aber auch irgendwie zu komplex.