Hola
Que aparezca un \( 1 \) el la posición \( i,j \) significa que el vértice \( i \) está unido con el \( j \).
Por tanto en tu caso se están uniendo todos los vértices pares con los impares, así que efectivamente se trata de un grafo bipartito \( K_{3,4} \).
No estoy seguro de que haya un método manejable y sistemático para calcular el polinomio cromático de cualquier grafo. Ahi alguna relación recursiva, que permite ir reduciendo el número de aristas pero en la práctica ese sistema es inviable por pesado.
En el caso de un grafo bipartito puedes razonar de la siguiente forma. Lo haré para tu caso particular, pero puede extenderse en general.
Supongamos que tenemos \( x \) colores. Si para los \( 3 \) vértices pares usamos \( y \) colores para los \( 4 \) restantes podremos usar \( x-y \) colores, y por tanto estos pueden colorearse de (x-y) formas distintas.
- Para y=1. Hay \( x \) formas de escoger 1 color entre los colore totales y una única forma de colorear los 3 vértices. Por tanto en este caso las formas posibles de colorear el grafo son:
\( x(x-1)^4 \)
- Para y=2. Hay \( x(x-1) \) formas de escoger 2 colores ordenados entre los colores totales. El primero se usará en un único vértice y el segundo en los otros dos. Hay tres formas de elegir cual es el vértice del color único. Por tanto en este caso las formas posibles de colorear el grafo son:
\( 3x(x-1)(x-1)^4 \)
- Para y=3. Hay \( x(x-1)(x-2) \) formas de escoger 3 colores ordenados entre los colores totales. En ese mismo orden los usamos para colorear los vértices 2,4,6. Por tanto en este caso las formas posibles de colorear el grafo son:
\( x(x-1)(x-2)(x-1)^4 \)
En definitiva el polinomio cromático es:
\( p(x)=x(x-1)^4+3x(x-1)^5+x(x-1)^5(x-2) \)
Hay una forma de sistematizar esto para cualquier grafo bipartito \( p,q \). Sólo hay que usar un poco de teoría combinatoria (no muy difícil si se ha cursado algo de matemática discreta) que involucra a los número de Stirling.
Saludos.
