-partito es un grafo cuyos vértices están o pueden ser particionados en
colores, de forma de que no haya puntos finales de esquinas que posean el mismo color.
, son llamados grafos bipartitos, y cuando
Los grafos bipartitos pueden ser reconocidos por tiempo polinómico, pero para cada
, este es NP-completo, dado un grafo incoloro, para probar si es
-partito puede ser dado como entrada a un cálculo con su coloración ya determinada; esto puede pasar cuando los conjuntos de los vértices en los grafos representan diferentes tipos de objetos.
Por ejemplo, las folcsonomías han sido modeladas matemáticamente por grafos tripartitos en los cuales los tres conjuntos de vértices del grafo representan usuarios de un sistema, recursos que los usuarios están etiquetando, y etiquetas que los usuarios han aplicado a los recursos.
-partito en el cual hay una esquina entre cada par de vértices de conjuntos independientes diferentes.
es el grafo tripartito completo de un octaedro regular, el cual puede ser particionado en tres conjuntos independientes, cada uno consistente de dos vértices opuestos.
[3] Los grafos de Turán son un caso especial de grafos multipartitos en los cuales cada dos conjuntos independientes difieren en tamaño por al menos un vértice.
-partitos completo, grafos multipartitos completos, y sus grafos complemento y los grafos racimo son casos especiales de cografos, y pueden ser reconocidos en tiempo polinómico incluso cuando la partición no es siministrada como parte de la entrada.