Demostrar o refutar el límite del número cromático.

Question

No estoy seguro de que esto sea cierto, ya que no puedo probarlo. Dejemos que $G$ sea un gráfico con número cromático $\chi(G)$ . Sea $D$ sea el conjunto de todos los vértices de $G$ con un grado de al menos $\chi(G)-1$ entonces $\chi(G) \leq |D|$ . Me cuesta ver por qué esto es cierto.

Si asumo que $\chi(G) > |D|$ entonces existe como máximo $\chi(G)-1$ elementos en $D$ . Por lo tanto, tiene que haber un vértice $v$ con $v \notin D$ . Este elemento sólo puede tener hasta $\chi(G)-2$ vecinos. Sin embargo, aquí es donde me quedo atascado al tratar de demostrar esto ya, pero también parece que no puedo encontrar un contraejemplo.

Answer 1

Una pista: Yo empezaría de la misma manera que tú; asumiendo que $\chi(G)>|D|$ . Esto significa que hay como máximo $\chi(G)-1$ vértices con un grado mínimo $\chi(G)-1$ . Obtendremos una contradicción al mostrar cómo colorear $G$ utilizando sólo $\chi(G)-1$ colores, contradiciendo la definición del número cromático.

La idea es la siguiente: empezar por colorear los vértices de $D$ con $\chi(G)-1$ colores distintos, lo que es posible ya que $|D|\le \chi(G)-1$ . A continuación, colorea el resto del grafo de vértice en vértice, eligiendo, para cada vértice, un color que no esté presente entre sus vecinos previamente coloreados. Como cada vértice que no está en $D$ tiene un grado como máximo $\chi(G)-2$ y hay $\chi(G)-1$ colores disponibles, siempre habrá al menos un color no presente en los vecinos de cada vértice. Por lo tanto, se puede colorear el resto del gráfico. ¡Contradicción!