grafos:ncromplano [WikiMat]

====== Número cromático do plano ======

Comecemos notando que o plano, $\mathbb{R}^2$, pode ser visto como um grafo em que cada ponto representa um vértice e arestas são segmentos de retas ligando dois pontos.\\

O número cromático do plano, denotado por $\chi(\mathbb{R}^2)$, é a quantidade mínima de cores suficientes para colorir o plano de modo que, para todo ponto de uma determinada cor, não exista nenhum ponto desta mesma cor a uma distância unitária dele. Noutras palavras, dados dois pontos a uma distância unitária, esses dois pontos têm cores distintas.

===== Soluções parciais =====

Até hoje não se sabe a resposta exata mas sabemos, com certeza, que $5\le\chi(\mathbb{R}^2)\le7$.

A seguir, mostraremos como são encontradas essas limitações para $\chi(\mathbb{R}^2)$.

----

=== Limitantes Superiores ===

Não é difícil apresentar quantidades de cores que são suficientes para colorir o plano de forma a satisfazer as regras do enunciado. O real desafio é encontrar o número **mínimo** de cores necessárias.

A fim de encontrar um valor preciso para o número cromático, faz sentido que limitemos --- superior e inferiormente --- $\chi(\mathbb{R}^2)$. Para obter bons limitantes superiores basta que organizemos as cores de forma inteligente.

A seguir mostraremos uma prova para $\chi(\mathbb{R}^2)\le9$ e, em seguida, para $\chi(\mathbb{R}^2)\le7$, que é o melhor limitante superior apresentado até o momento.

Note que, se particionarmos o plano em quadrados iguais tais que a circunferência que os circunscreve tenha diâmetro $d:$ $\frac{\sqrt{2}}{2}<d<1$ ($\frac{\sqrt{2}}{2}\approx0,71$) e colorirmos de forma periódica cada bloco de 9 quadrados de forma que cada um deles possui uma cor diferente entre si, obtemos um plano "9-colorido" onde dado $x\in\mathbb{R}^2$ qualquer não há nenhum elemento $y$ de cor igual a $x$ tal que $\operatorname{d}(x,y)=1$. A seguir, vemos que o número cromático do plano é menor ou igual a 9.

{{ :grafos:tilingpontos.png?300 |}}

Seguindo esta mesma ideia, Hadwiger conseguiu mostrar que uma construção similar é possível com hexágonos regulares de diâmetro  $d:\underset{\underset{0,77}{\approx}}{\frac{4\sqrt{3}}{9}}<d<1$. Agora, notamos que o número cromático do plano é menor ou igual a 7 (construção de Hadwiger), como vemos abaixo.

{{ :grafos:hextilingpontos.png?300 |}}

----

=== Limitantes Inferiores ===

Para mostrar que $k$ é um limitante inferior, basta exibir um grafo no plano que não seja $(k-1)$-colorível.

{{ :grafos:altmoser.png?300|}}

Os primeiros casos são, de certa forma, triviais. A primeira prova mais sofisticada surge somente onze anos após a formulação do problema. Os irmãos Moser criaram o que ficou conhecido como //Moser spindle//, ilustrado ao lado.



Quase sessenta anos depois da descoberta dos Moser, em 2018, um biólogo --- autoproclamado matemático amador --- faz um novo avanço no problema. Com assistência da programação, Aubrey de Grey começa a montar grafos com alta "densidade spindle" e os colorir com algorítmos computacionais.

Em seu artigo, Aubrey encontra, inicialmente, um grafo com 20425 vértices que não é $4$-colorível. Com algumas técnicas de enxugamento ele obtém uma nova versão, agora com 1581 vértices.

Os esforços de Aubrey foram de muita ajuda pois, em 2019, Marijn Heule usa os trabalhos do biólogo para gerar derivações dos grafos que também não são 4-coloríveis mas possuem menos vértices. O progresso mais recente de Heule foi de um grafo com apenas 510 vértices.

Num período de menos de um ano, Jaan Parts refina ligeiramente o então menor grafo não 4-colorível. Novamente replicando as técnicas de de Grey, Parts consegue exibir um grafo com 509 vértices. Abaixo vemos o grafo de Heule com 517 vértices --- apenas para fins ilustrativos.

{{ :grafos:517.png?600 |}}