===== O número de cores de um grafo =====

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:

<WRAP round box 70%>
=== Proposição ===
Um grafo $G$ com $m$ arestas satisfaz 

$$k= \chi(G) \leq \frac{1}{2} + \sqrt{2m + \frac{1}{4}}$$

onde:
  * $\chi(G)$ é a [[.coloracao | número cromático (vertice) de $G$]].

</WRAP>


<WRAP round box 100%>
//**Demonstração:**//
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. 

Se, por exemplo, temos $1,2$ e $3$ componentes conexas como na imagem a seguir:

{{:grafos:tri.jpg?400|}}

Vemos que a situação é 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, resolvendo para $k$, podemos calcular a raiz da equação:

$$k \leq \frac{1}{2} + \sqrt{2m + \frac{1}{4}}$$

<wrap right>$\square$</wrap>
</WRAP>

----

<WRAP round info 100%>
=== Referências ===
  * Reinhard Diestel. [[https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch5.pdf|“Graph Theory”]] .5th Electronic Edition 2016, pp. 122. Acesso em 12/06/2023.

</WRAP>