K-partiter Graph
Ein k-partiter Graph ist in der Graphentheorie ein einfacher Graph, dessen Knotenmenge in k disjunkte Teilmengen zerfällt, so dass die Knoten jeder dieser Teilmengen untereinander nicht benachbart sind. Insofern stellt dies eine Verallgemeinerung der bipartiten Graphen dar, für die k=2 verlangt wird.
Jeder k-partite Graph ist auch immer ein k+x-partiter Graph, wobei x eine natürliche Zahl und k+x kleiner als die Knotenzahl ist.
Formal
Ein Graph G=(V,E) heißt k-partit, falls 
eine Partition von V ist und
.Man beachte, dass die Partition nicht eindeutig ist. Es ist durchaus möglich, dass es mehrere Partitionen gibt, die diese Eigenschaft erfüllen.
Man nennt den Graphen dann vollständig k-partit falls außerdem
.Mit 
notiert man einen vollständig k-partiten Graphen, mit | Vi | = ni.