多分图

在数学的分支图论中，一个 k-分图是一个图，其点集被分成 k 部分，各部分各自形成独立集。换句话说，可以把图的所有点着色，使得相邻的点着不同色且总共用了k 个颜色。k = 2 的情况被称作二分图，而 k = 3 的情况被称作三分图。

特殊种类的完全 k-分图

K2,2,2	K3,3,3	K2,2,2,2
由正八面体的顶点和边组成的图	由复广义正八面体的顶点和边组成的图	由正十六胞体的顶点和边组成的图

事实上，辨别一个图是二分图只需要多项式时间。但当 k > 2，辨别一个图是否为 k-分图却是NP完全的 。不过，在一些图论的应用场合中，给计算器处理 k-分图会包含 k 个部分的划分，比如说各个部分所代表的是不同类型的物件。例如可以用三分图做大众分类法的数学模型，三个部分分别为系统的使用者、系统拥有的资料来源、使用者给资料来源的标签。

一个完全 k-分图是一个 k-分图，其中两点若属于相异的部分则必相邻。该图的记为一个大写 K，在下标标注个部分的顶点数，并用英文逗号分开。例如 K_2,2,2 可以想成正八面体的顶点和边，其中三个独立集使三组对顶点。所有的完全 k-分图统称为完全多分图。图兰图是一种特殊的完全多分图，其中各部分的顶点数至多差 1。