Graf k-dzielny

Graf k-dzielny – naturalne rozszerzenie klasy grafów dwudzielnych - jest to graf, którego zbiór wierzchołków można podzielić na k parami rozłącznych podzbiorów takich, że żadne dwa węzły należące do tego samego zbioru nie są połączone krawędzią^[1].

Innymi słowy, jeżeli ${\displaystyle \!G}$ jest grafem k-dzielnym, to na zbiorze jego wierzchołków ${\displaystyle \!V(G)}$ istnieje podział:

${\displaystyle \!V(G)\ =\ \bigcup _{i\in 1\cdots k}V_{i}(G)}$

taki, że

${\displaystyle \!\forall _{u,v\in V_{i}(G)}\{u,v\}\notin E(G)}$

• Eric W.E.W. Weisstein Eric W.E.W., k-Partite Graph, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).