Problema de Hadwiger–Nelson

Pla amb hexàgons de 7 colors, i un graf de distància unitària al pla (el graf de Moser), demostrant que el nombre cromàtic està fitat entre 4 i 7.

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. La resposta és desconeguda, però s'ha reduït a poques possibilitats: 5, 6 o 7.

Relació amb els grafs finits

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.

Vegeu també

• Teoria de grafs
• Teoria de conjunts
• Problema dels quatre colors