Grafo multipartito

En teoría de grafos, un grafo $k$-partito es un grafo cuyos vértices están o pueden ser particionados en $k$ diferentes conjuntos independientes. Equivalentemente, es un grafo que puede ser coloreado con $k$ colores, de forma de que no haya puntos finales de esquinas que posean el mismo color. Cuando $k=2$, son llamados grafos bipartitos, y cuando $k=3$, tripartitos.

Los grafos bipartitos pueden ser reconocidos por tiempo polinómico, pero para cada $k>2$, este es NP-completo, dado un grafo incoloro, para probar si es $k$-partito.​ Sin embargo, en algunas aplicaciones de la teoría de grafos, un grafo $k$-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.​

Ejemplos de grafos $k$-partitos completos

$K_{2,2,2}$	$K_{3,3,3}$	$K_{2,2,2,2}$
Grafo de un octaedro	Grafo de un octaedro generalizado complejo	Grafo de un hexadecacoron

Un grafo $k$-partito completo es un grafo $k$-partito en el cual hay una esquina entre cada par de vértices de conjuntos independientes diferentes. Estos grafos están denotados con una $K$ mayúscula, seguida de un subíndice 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, el cual puede ser particionado en tres conjuntos independientes, cada uno consistente de dos vértices opuestos. Un grafo multipartito completo es un grafo que es completamente $k$-partito para algún $k$.​ 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. Los grafos $k$-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.

Referencias

• Datos: Q30904191