Como determinamos o número cromático de um determinado grafo? Como podemos encontrar uma coloração de vértice com o menor número de cores possível? Como o número cromático se relaciona com outras invariantes do grafo, como grau médio, conectividade ou perímetro?

Diretamente da definição de número cromático podemos derivar o seguinte limite superior:

Dem 1:

Vamos visualizar que se temos $1,2$ e $3$ componentes conexas como na imagem a seguir

é uma $3$-coloração, contudo se não existisse a aresta $1$-2, então poderíamos trocar a cor do $2$ para a cor do $1$, ou vice versa, tendo assim uma $2$-coloração.

Dessa forma o número de arestas $m$ de um grafo $G$, possui a seguinte relação:

$$m \geq \binom{k}{2} = \frac{k(k-1)}{2}$$

Assim podemos calcular a raiz da equação:

• $K \leq \frac{1}{2} + \sqrt{\frac{1}{4} + 2m}$ $\square$

Dem 2:

Seja $\mathcal{c}$ uma coloração de vértice de $G$ com $k=\chi(G)$ cores. Então $G$ tem pelo menos uma aresta entre quaisquer duas classes de cores: caso contrário, poderíamos ter usado a mesma cor para ambas as classes. Assim, $m \geq \frac{1}{2} k(k-1)$. Resolvendo esta desigualdade para $k$, obtemos a afirmação reivindicada.