Burnsides Lemma richtig angewendet? Färbung von Graphen

Question

Aufgabe:

Auf wie viele Arten können die Ecken eines Kreises mit 5 Ecken gefärbt werden, wenn 3 Farben verwendet werden dürfen?

Ansatz:

Ich bestimme die Automorphismengruppe des Kreisgraphen K₅. Dann zähle ich die Fixpunkte (Burnside).

Aut(K₅)={id, s₁, s₂, s₃, s₄, s₅, r₁, r₂, r₃, r₄}, wobei s_i die Spiegelungen und r_i die Rotationen sein sollen.

Fixpunkte:

- id: 3⁵

- s_i: 3³ , wir haben 5 Spiegelungen also 5* 3³

- r_i: 3¹, wir haben 4 Rotationen also 4*3

Insgesamt \( \frac{1}{10} \) (3⁵+5*3³+4*3)=39

Comments

Hallo,

das chromatische Polynom von \(C_5\) ist \(\chi(\lambda)=(\lambda-1)^5+1-\lambda\). Für \(\lambda=3\) erhält man \(\chi(5)=30\).

---

Chromatisches Polynom hatten wir noch nicht … hast du vielleicht einen anderen Ansatz ? vielen Dank schonmal

---

Lemma von Burnside kann man machen, ich schaue es mir später mal genauer an. Bin gerade kognitiv nicht auf der Höhe.

---

Das Lemma von Burnside habe ich ja auch verwendet. Aber ich komme auf 39

---

Ich glaube, du zählst zu viele Spiegelungen.

---

Aber es sind doch insgesamt 5 Spiegelachsen. Einmal durch jede Ecke. In der Permutationsschreibweise sieht man auch, dass es 5 verschiedene Spiegelungen sind...

---

Aber warum hoch 3?

---

Weil in den SPiegelungen 3 Zykel vorkommen.