Die Graphentheorie entwickelte sich seit Ende des 19. Jahrhunderts aus dem klassischen Vier-Farben-Problem. Dieses ist ein spezieller Fall des allgemeinen Problems, die Knoten eines Graphen so zu färben, dass durch eine Kante verbundene Knoten jeweils mit unterschiedlichen Farben gefärbt sind. Die Anzahl der Möglichkeiten, einen gegebenen Graphen G so mit n Farben zu färben, bezeichnet…
Im letzten Beitrag hatten wir über Färbungen von Graphen geschrieben und darüber, dass das chromatische Polynom stets unimodal ist, also seine Koeffizienten erst steigen und dann fallen. Zum Beispiel hat der vollständige Graph auf fünf Knoten K5 das chromatische Polynom x5-10×4+35×3-50×2+24x oder der bipartite Graph K2,3 das chromatische Polynom x5-6×4+15×3-17×2+7x oder der Petersen-Graph das Polynom…
Letzte Kommentare