Coloración fraccionada
La coloración fraccionada es un tema en una rama joven de la teoría de grafos conocida como teoría de grafos fraccionarios . Es una generalización de la coloración de gráficos ordinaria . En una coloración de gráfico tradicional, a cada vértice de un gráfico se le asigna un color, y a los vértices adyacentes, los que están conectados por bordes, se les deben asignar colores diferentes. Sin embargo, en una coloración fraccionada, se asigna un conjunto de colores a cada vértice de un gráfico. El requisito sobre los vértices adyacentes todavía se mantiene, por lo que si dos vértices están unidos por un borde, no deben tener colores en común.
La coloración de gráficos fraccionada se puede ver como la relajación de programación lineal de la coloración de gráficos tradicional. De hecho, los problemas de coloración fraccionada son mucho más fáciles de aplicar con un enfoque de programación lineal que los problemas de coloración tradicionales.
Una coloración b- pliegue de un gráfico G es una asignación de conjuntos de tamaño b a los vértices de un gráfico de modo que los vértices adyacentes reciben conjuntos disjuntos. Una un : b -Coloreado es un b -fold coloración de un colores disponibles. De manera equivalente, se puede definir como un homomorfismo al gráfico de Kneser KG a , b . El b -fold número cromática es el menos una de tal manera que una un : b existe -Coloreado.
El número cromático fraccionario se define como
Tenga en cuenta que el límite existe porque es subaditivo , es decir
El número cromático fraccionario se puede definir de manera equivalente en términos probabilísticos. es el k más pequeño para el que existe una distribución de probabilidad sobre los conjuntos independientes de G tal que para cada vértice v , dado un conjunto independiente S extraído de la distribución,
