Dejemos que $G$ y $H$ sean dos grafos conectados (finitos y simples) con la misma secuencia de grados. ¿Es posible hacer $|\chi(G) - \chi(H)|$ arbitrariamente grande eligiendo las $G$ y $H$ ?
Respuesta
¿Demasiados anuncios?
Dejemos que $G$ sea el grafo bipartito completo $K_{n/2,n/2}$ y que $H$ consisten en dos copias de $K_{n/2}$ con una correspondencia perfecta entre ellos. (La coincidencia perfecta hace que $H$ conectado y lleva sus grados hasta el valor correcto).
Entonces $G$ y $H$ ambos tienen la secuencia de grados $(n/2, n/2, \dots, n/2)$ pero $\chi(G) = 2$ y $\chi(H) = n/2$ .
(También se puede pensar en $H$ como el producto gráfico $K_{n/2} \square K_2$ .)
