Question

Wie lautet das chromatische Polynom des vollständig bipartiten Graphen?

Erste Frage Aufrufe: 87 Aktiv: 28.01.2025 um 21:06

Jetzt Frage stellen

0

Meine Idee:

$P(K_{m,n}) = \lambda ^ m (\lambda - m) ^ n$

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

Edit: Meine Lösung ist garantiert falsch, da für $m = \lambda = 2$ in jedem Fall 0 herauskommen würde, was unlogisch ist, da ein bipartiter Graph in jedem Fall eine zulässige 2-Färbung besitzt.

Teilen Diese Frage melden

gefragt 27.01.2025 um 19:31

mssro
Punkte: 10

chatGPT sagt $P_{Km,n}(k)=k⋅(k−1)^m⋅(k−1)^n$ und erklärt es auch. Probier mal. ─ mikn 27.01.2025 um 19:49

Dieses Ergebnis ist aber falsch.

Für den vollständig bipartiten Graphen $K_{2, 3}$ gilt:

$P(K_{2, 3}) = k (k-1) (k^3 - 5k^2 + 10k - 7)$

(Quelle: https://math.stackexchange.com/questions/676754/chromatic-polynomial-for-a-bipartite-graph)

Setze ich $m = 2$ und $n = 3$ in der ChatGPT Lösung, erhält man:

$k(k-1)^2 (k-1)^3 = k(k-1)(k-1)^4$

Jedoch:

$(k-1)^4 \neq k^3 - 5k^2 + 10k - 7$ ─ mssro 27.01.2025 um 20:32

Interessant. Ich hab das nicht geprüft. Eine andere KI liefert $k^m(k-1)^n+k^n(k-1)^m$, was aber dann auch nicht passt. ─ mikn 27.01.2025 um 22:10

Kommentar schreiben

1 Antwort

Jetzt Antwort schreiben

m.simon.539 · Answer 1 · 2025-01-28T17:07:15Z

Man muss berücksichtigen, dass, wenn man nicht alle Farben in der ersten Partion verwendet, man für dir zweite Partition mehr Auswahl hat.
Also:
Um k Farben aus einer Palette von $\lambda$ Farben auszuwählen, gibt es $\binom{\lambda}{k}$ Möglichkeiten, wobei $1\le k\le\lambda$.
Um die erste Partition mit max. k Farben einzufärben, die aus einer Palette von $\lambda$ Farben gewählt werden dürfen,
gibt es $\binom{\lambda}{k} k^m$ Möglichkeiten, wobei m=Anzahl der Knoten in 1. Partition.
Um die erste Partition mit GENAU k Farben einzufärben, die aus einer Palette von $\lambda$ Farben gewählt werden dürfen,
gibt es $\displaystyle \binom{\lambda}{k} k^m - \binom{\lambda}{k-1} (k-1)^m$ Möglichkeiten, wobei m=Anzahl der Knoten in 1. Partition.

Die zweite Partition kann dann mit den verbleibenden $\lambda-k$ Farben eingefärbt werden: $(\lambda-k)^n$ Möglichkeiten.
Also lautet das charakteritische Polynom
$\displaystyle p(\lambda) = \sum_{k=1}^{\lambda} \left( \binom{\lambda}{k} k^m - \binom{\lambda}{k-1} (k-1)^m \right) (\lambda-k)^n$.

Für $m=n=\lambda=2$ ergibt sich z.B.:
$\displaystyle p(2) \;=\; \sum_{k=1}^{2} \left( \binom{2}{k} k^2 - \binom{2}{k-1} (k-1)^2 \right) (2-k)^2$
$\displaystyle = \; \left( \binom{2}{1} \cdot 1^1 - \binom{2}{0} 0^2 \right) \cdot 1^2 + \left( \binom{2}{2} \cdot 2^1 - \binom{2}{1} 1^2 \right) \cdot 0^2$
$= \; \left(2 \cdot 1 - 1 \cdot 0 \right) \cdot 1 = 2$.
Das sind die beiden Färbungen
1. Erste Partition Farbe 1, zweite Partition Farbe 2
2. Erste Partition Farbe 2, zweite Partition Farbe 1