Prueba de $\chi(G)\leq 1+\max_i\min\{d_i,i-1\}$ en teoría de grafos

Question

Estoy aprendiendo un teorema de coloración en teoría de grafos:

Si un gráfico $G$ tiene secuencia de grados $d_1\geq\cdots\geq d_n$ entonces $\chi(G)\leq 1+\max_i\min\{d_i,i-1\}$ .

La prueba del libro consta de 4 frases:

1. Aplicamos una coloración codiciosa a los vértices en orden no creciente de grado.
2. Cuando coloreamos el $i$ vértice $v_i$ tiene como máximo $\min\{d_i,i-1\}$ vecinos anteriores, y como máximo este número de colores aparecen en sus vecinos anteriores.
3. De ahí el color que asignamos a $v_i$ es como máximo $1+\min\{d_i,i-1\}$ .
4. Esto se cumple para cada vértice, por lo que maximizamos sobre $i$ para obtener el límite superior del color máximo utilizado.

---

En coloración codiciosa en relación con una ordenación de vértices $v_1,\cdots,v_n$ de $V(G)$ se obtiene coloreando los vértices en el orden $v_1,\cdots,v_n$ asignando a $v_i$ el color de menor índice que no se haya utilizado ya en sus vecinos de menor índice.

---

No entiendo la primera frase de la prueba: ¿Dónde usamos el orden de grado no creciente en el resto de la prueba?

Answer 1

En el contexto "coloración codiciosa" debe significar algo así como:

1. Asigna colores a los vértices empezando por los de mayor grado y terminando por los de menor grado.
2. Para cada vértice, dale el color con el número más bajo que aún no se haya asignado a ninguno de sus vecinos.

El orden de grado no creciente no es en realidad usado en el profe sin esa condición, la prueba funcionaría igual de bien para demostrar:

Si un gráfico $G$ tiene nodos de grado $d_1, d_2, \ldots, d_n$ entonces $\chi(G)\le 1+\max_i \min(d_i,i-1)$ .

La idea de ordenar primero los vértices de mayor grado es que así se obtiene la mejor oportunidad para $\max_i\min(d_i,i-1)$ para ser un número pequeño, y por lo tanto da un límite más fuerte en el número cromático.

La clave es el $\min(d_i, i-1)$ . Usted quiere evitar que esto se convierta en grande - es decir, usted quiere evitar cualquier vértice donde $d_i$ y $i-1$ son ambos números grandes. La forma más sencilla de hacerlo es asegurarse de que los vértices con un gran $d_i$ tienen un $i$ como se les puede dar -- es decir, los vértices con alto grado deben venir primero en la lista.