imported>회기-로: Ist bereits im Artikel verlinkt. Die letzte Textänderung von Arget93 wurde verworfen und die Version 149418091 von 부고 wiederhergestellt.

2021-03-09T14:29:22Z

Ist bereits im Artikel verlinkt. Die letzte Textänderung von Arget93 wurde verworfen und die Version 149418091 von 부고 wiederhergestellt.

Neue Seite

Die '''chromatische Zahl''' <math>\chi(G)</math> (auch '''Knotenfärbungszahl''' oder kurz '''Färbungszahl''', selten auch '''Farbzahl''' genannt) eines [[Graph (Graphentheorie)|Graphen]] ist die kleinste Zahl <math>k</math>, für die der Graph eine zulässige [[Knotenfärbung]] mit <math>k</math> Farben besitzt. (Eine Färbung heißt zulässig oder gültig, wenn es keine benachbarten Knoten gibt, die mit der gleichen Farbe gefärbt sind.) Die chromatische Zahl ist zugleich die kleinste natürliche Zahl λ, für die das [[Chromatisches Polynom|chromatische Polynom]] <math>\chi(G,\lambda)\neq 0</math> ist.

Die '''achromatische Zahl''' <math>\psi (G)</math> eines Graphen <math>G</math> ist die größte Zahl <math>k</math>, für die <math>G</math> eine gültige und vollständige Knotenfärbung mit <math>k</math> Farben hat. (Eine Färbung heißt vollständig, wenn es zu jedem Paar von verschiedenen Farben eine Kante gibt, deren Endknoten mit diesen beiden Farben gefärbt sind.)

Die '''pseudo-achromatische Zahl''' <math>\psi_s (G)</math> eines Graphen <math>G</math> ist die größte Zahl <math>k</math>, für die <math>G</math> eine vollständige Knotenfärbung hat. Im Gegensatz zur achromatischen Zahl ist hier nicht die Gültigkeit der Färbung verlangt.

== Siehe auch ==
* [[Chromatischer Index]] (Kantenfärbungszahl)

[[Kategorie:Graphentheorie]]

Chromatische Zahl - Versionsgeschichte

imported>회기-로: Ist bereits im Artikel verlinkt. Die letzte Textänderung von Arget93 wurde verworfen und die Version 149418091 von 부고 wiederhergestellt.