Lexikon der Mathematik: k-partiter Graph
ein GraphG, dessen Eckenmenge E(G) in k ≥ 2 paarweise disjunkte Eckenmengen E1, E2, …, Ek so zerlegt werden kann, daß die von den Eckenmengen Ei induzierten Teilgraphen für alle 1 ≤ i ≤ k leere Graphen sind. Man nennt dann E1, E2, …, Ek die Partitionsmengen des k-partiten Graphen.
Ein k-partiter Graph heißt vollständig k-partit, wenn alle Ecken aus verschiedenen Partitionsmengen paarweise untereinander adjazent sind. Im Fall k = 2 spricht man auch von einem bipartiten bzw. vollständigen bipartiten Graphen.
Die k-partiten Graphen sind eng mit der Eckenfärbung verknüpft. Denn für die chromatische Zahl χ(G) eines Graphen G gilt genau dann χ(G) = k ≥ 3, wenn G ein k-partiter, aber kein (k − 1)-partiter Graph ist.
Darüber hinaus gilt χ(G) = 1 genau dann wenn G ein leerer Graph, und χ(G) = 2, wenn G kein leerer, aber ein bipartiter Graph ist.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.