En teoría de grafos , una parte de las matemáticas, un grafo k -partito es un grafo cuyos vértices están (o pueden estar) divididos en k conjuntos independientes diferentes . De manera equivalente, es un grafo que puede colorearse con k colores, de modo que no haya dos extremos de una arista con el mismo color. Cuando k = 2, estos son los grafos bipartitos , y cuando k = 3, se denominan grafos tripartitos .
Los grafos bipartitos pueden reconocerse en tiempo polinomial pero, para cualquier k > 2, es NP-completo , dado un grafo sin color, para comprobar si es k -partito. [1] Sin embargo, en algunas aplicaciones de la teoría de grafos, un grafo k -partito puede proporcionarse como entrada a un cálculo con su coloración ya determinada; esto puede suceder cuando los conjuntos de vértices del grafo representan diferentes tipos de objetos. Por ejemplo, las folksonomías se han modelado matemáticamente mediante grafos tripartitos en los que 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. [2]
Un grafo k -partito completo es un grafo k -partito en el que hay una arista entre cada par de vértices de diferentes conjuntos independientes. Estos grafos se describen mediante notación con una letra K mayúscula subíndice por una secuencia de los tamaños de cada conjunto en la partición. Por ejemplo, K 2,2,2 es el grafo tripartito completo de un octaedro regular , que se puede dividir en tres conjuntos independientes, cada uno de los cuales consta de dos vértices opuestos. Un grafo multipartito completo es un grafo que es k -partito completo para algún k . [3] Los grafos de Turán son el caso especial de grafos multipartitos completos en los que cada dos conjuntos independientes difieren en tamaño como máximo en un vértice. Los grafos k -partitos completos, grafos multipartitos completos y sus grafos complementarios , los grafos de conglomerados , son casos especiales de cografos y se pueden reconocer en tiempo polinomial incluso cuando la partición no se suministra como parte de la entrada.