Conexión entre el número cromático y la independencia de un gráfico

Question

¿Es verdad que uno siempre puede color de un gráfico G con $\chi(G)$ colores de tal manera que una de las clases de color es un conjunto independiente máximo posible cardinalidad? Por favor, probar si es verdad.

[Nota: $\chi(G)$ es el número cromático de G, o el más pequeño número k tal que podemos color del gráfico G con k colores. Conjunto independiente significa que ninguno de los vértices en el conjunto son adyacente.

Answer 1

No es verdad. Por favor acepte este contraejemplo humilde pintura.

A la izquierda, vemos que la gráfica es 3-colorable. A la derecha, tomar el conjunto independiente de cardinalidad máxima y que sea todo azul, luego se atascan con los dos colores restantes.