Uma maneira óbvia de colorir um grafo $G$ com poucas cores é o seguinte algoritmo guloso: começando de uma enumeração fixa $v_1, \dots, v_n$ de $G$, consideramos os vértices por sua vez e colorimos cada $v_i$ com as primeiras cores disponíveis, ou seja, com o menor valor positivo inteiro ainda não usado para colorir qualquer vizinho de $v_i$ entre $v_1, \dots, v_{i-1}$. Desta forma, nunca usamos mais que $\Delta (G)+1$ cores, mesmo para escolhas desfavoráveis ​​da enumeração $v_1, \dots, v_n$. Se $G$ for completo ou um ciclo ímpar, então isso é ainda melhor possível.

Em geral, este limite superior de $\Delta (G)+1$ é bastante generoso mesmo para colorações gulosas. De fato, quando vamos colorir o vértice $v_i$ no algoritmo acima, precisamos apenas de um suprimento de cores $d_{G[v_1, \dots, v_i]}(v_i)+1$ em vez de $d_{G}(v_i)+1$ para prosseguir; lembre-se que, neste estágio, o algoritmo ignora quaisquer vizinhos $v_j$ de $v_i$ com $j >i$. Portanto, na maioria dos grafos, haverá espaço para uma melhoria do limite $\Delta +1$, escolhendo uma ordem de vértice particularmente adequada para começar: uma que escolha os vértices de alto grau no início (quando a maioria dos vizinhos é ignorada) e os vértices de pequeno grau por último. Localmente, o número $d_{G[v_1, \dots, v_i]}(v_i)+1$ de cores necessárias será menor se $v_i$ tiver grau mínimo em $G[v_1, \dots, v_i]$. Mas isso é facilmente alcançado: basta escolher $v_n$ primeiro, com $d(v_n) = \delta (G)$, depois escolher como $v_{n-1}$ um vértice de grau mínimo em $G-v_n$ , e assim por diante.

O último número $k$ tal que $G$ tem uma enumeração de vértice na qual cada vértice é precedido por menos de $k$ de seus vizinhos é chamado de número de coloração $col(H)$ de $G$. A enumeração que acabamos de discutir mostra que $col(G) \leq max_{H \subseteq G} \delta (H) +1$. Mas para $H \subseteq G$ claramente também $col(G) \geq col(H)$ e $col(H) \geq \delta (H)+1$, já que o grau anterior do último vértice em qualquer enumeração de $H$ é apenas seu grau comum em $H$, que é pelo menos $\delta (H)$. Portanto, provamos o seguinte:

Observação: O número de cores do grafo está próximo de sua arboricidade; veja o Teorema de Nash-Williams.

Para realizarmos uma coloração precisamos escolher um determinado método para ela, para isso começaremos escolhendo um vértice e criaremos uma sequência a partir dele , dessa forma iremos colorir cada $v_i$ em ordem, com isso $k \leq$ $\Delta(G)$ + 1.

• Para melhorar tal algorítmo iremos procurar por uma ordenação que diminua o número de cores, assim optaremos por escolher os vértices de grau maior antes, de maneira que o último vértice obedeça $\delta(v_n) = $ $\delta(G)$ e $d(v_{n-1})$ $= \delta(G \setminus v_n)$ e assim por diante.
• Assim $Col(G)$ é o menor $k$ tal que existe uma ordem sobre $G$ que todo $v$ possui menos que $k$ adjacentes de grau menor.