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 jest grafem k-dzielnym, to na zbiorze jego wierzchołków istnieje podział:
taki, że