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.