Estoy investigando gráfico para colorear problema.
Pero no puedo encontrar ninguna solución sobre el problema con un número limitado de cada uno de los colores. Quiero decir, Supongamos que tres colores(verde, rojo, azul) y un gráfico, podemos empezar a color de cada vértice, pero (Si el color verde del límite es 3) no podemos colores como el verde después de que ya hemos usado en verde 3 veces.
Cualquier comentario acerca de este problema será apreciado. En cualquiera de los documentos, artículos, o tal vez la solución en sí misma.
Gracias por adelantado.
Para simplificar y aclarar la pregunta, me esta pensada una gruesa ejemplo.
(vértice para colorear. NO borde de colorear)
1) Tenemos 3 colores, digamos, verde, azul, rojo. Y la gráfica es una línea. Cada vértice tiene dos aristas, excepto dos(=inicio de uno, y al final uno). Me refiero a esto : ○-○-○-○-○-○-○. $V$ es el vértice número. En este caso,$V=7$. Empezamos a colorear cada vértice, pero el límite es de 3, 2, 2.(Por simplicidad, la suma de los límites de la misma con el número de vértices.) Por lo que podemos utilizar sólo 3 verdes, 2 azules, 2 rojos.(Seguramente todos los colores no deben ser adyacentes).
La respuesta debe ser 38.(encontrado por la comprobación de todas las combinaciones)
2) ¿Cómo sobre un anillo gráfico( así que todos los vértices tienen dos bordes). en el caso anterior?
3) ¿qué tal perterson gráfico con los límites de 4, 3, 3?
No espero que el elegante($\approx$corto) solución. Tengo curiosidad acerca de la manera de cómo resolver esto correctamente, y desean romper con este problema sin encontrar de TODOS los casos posibles y comprobar uno por uno. Tal vez algunos (tedioso) $nCr$s, sería agradable. Si el vértice y el número de colores son limitados(por ejemplo. $<1000$), el tiempo de complejidad, pudieran no ser un gran problema. (No podemos comprobar todos los casos, incluso en este pequeño tamaño. La combinación de la complejidad está en el factorial de orden.$\approx 1000!$) Creo que esto puede ser posible mediante el uso de la progresión, la inducción o algo por el estilo.
