Problema de Hadwiger–Nelson
En teoria de grafs, el problema de Hadwiger–Nelson, anomenat així per Hugo Hadwiger i Edward Nelson, demana el nombre mínim de colors necessari per acolorir el pla de manera que no hi hagi dos punts a la distància 1 l'un de l'altre que tinguin el mateix color.[1][2] La resposta és desconeguda, però s'ha reduït a poques possibilitats: 5, 6 o 7.[3]
Relació amb els grafs finits
[modifica]El problema es pot reformular en termes més generals de la teoria de grafs de la següent manera. Definim G com el graf amb distància unitària: un graf infinit amb tots els punts del pla com a vèrtexs i amb una connexió entre dos vèrtexs si i només si la distància entre els dos punts és 1. El problema de Hadwiger–Nelson és trobar el nombre cromàtic de G. Emprant el teorema de De Bruijn–Erdős, el problema és equivalent (sota el supòsit de l'axioma d'elecció) al de trobar el nombre cromàtic més gran possible d'un graf de distància finit unitari.[4]
Referències
[modifica]- ↑ Hadwiger, Hugo (1945), "Überdeckung des euklidischen Raumes durch kongruente Mengen", Portugal. Math. 4: 238–242
- ↑ Gardner, Martin (1960), "Mathematical Games", Scientific American 203/4: 180
- ↑ Aaronson, Scott (April 11, 2018), Amazing progress on longstanding open problems, <https://www.scottaaronson.com/blog/?p=3697>
- ↑ de Bruijn, N. G. & Erdős, P. (1951), "A colour problem for infinite graphs and a problem in the theory of relations", Nederl. Akad. Wetensch. Proc. Ser. A 54: 371–373, DOI 10.1016/S1385-7258(51)50053-7