ein Graph G, dessen Eckenmenge E(G) in k ≥ 2 paarweise disjunkte Eckenmengen E₁, E₂, …, E_k so zerlegt werden kann, daß die von den Eckenmengen E_i induzierten Teilgraphen für alle 1 ≤ i ≤ k leere Graphen sind. Man nennt dann E₁, E₂, …, E_k 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.