La pregunta puede formularse en términos de la teoría de grafos de la siguiente manera. Sea G el gráfico de distancia unitaria del plano: un grafo infinito con todos los puntos del plano como vértices y con una arista entre dos vértices si, y solo si, la distancia entre los dos puntos es 1. El problema de Hadwiger-Nelson consiste en hallar la coloración de grafos de G. Como consecuencia, el problema suele denominarse "hallar el número cromático del plano". Según el teorema de De Bruijn-Erdős, un resultado de de Bruijn y Erdős (1951), el problema es equivalente (bajo el supuesto del axioma de elección) a encontrar el mayor número cromático posible de un grafo de distancias unitarias finitas.

Según Jensen y Toft (1995), el problema fue formulado por primera vez por Nelson en 1950 y publicado por primera vez por Gardner (1960). Hadwiger (1945) había publicado previamente un resultado relacionado, que demostraba que cualquier recubrimiento del plano por cinco conjuntos cerrados congruentes contiene una distancia unitaria en uno de los conjuntos, y también mencionó el problema en un artículo posterior (Hadwiger, 1961). Soifer (2008) analizó el problema y su historia extensamente.

Una aplicación del problema lo conecta con el teorema de Beckman-Quarles, según el cual cualquier aplicación del plano euclídeo (o cualquier espacio de dimensión superior) sobre sí mismo que preserve las distancias unitarias debe ser una isometría, que preserva todas las distancias.^[2]​ Las coloraciones finitas de estos espacios permiten construir aplicaciones a partir de ellos en espacios de dimensiones superiores que conservan las distancias, pero no son isometrías. Por ejemplo, el plano euclídeo se puede aplicar a un espacio de seis dimensiones coloreándolo con siete colores, de modo que ningún par de puntos a una distancia dada de un color tenga el mismo color, y luego aplicando los puntos, según sus colores, a los siete vértices de un símplex de seis dimensiones con aristas de longitud unitaria. Esto aplica dos puntos cualesquiera a una distancia de un color a colores distintos, y de ahí a vértices distintos del símplex, separados por una distancia unitaria. Sin embargo, aplica todas las demás distancias a cero o uno, por lo que no es una isometría. Si el número de colores necesarios para colorear el plano se pudiera reducir de siete a un número menor, la misma reducción se aplicaría a la dimensión del espacio objetivo en esta construcción.^[3]​

El hecho de que el número cromático del plano debe ser al menos cuatro se desprende de la existencia de un grafo de distancia unitaria de siete vértices con número cromático cuatro, llamado huso de Moser tras su descubrimiento en 1961 por los hermanos William y Leo Moser. Este grafo consta de dos triángulos equiláteros unitarios unidos en un vértice común, "x". Cada uno de estos triángulos está unido por otra arista a otro triángulo equilátero; los vértices "y" y "z" de estos triángulos unidos están a una distancia unitaria entre sí. Si el plano pudiera ser tricolor, la coloración dentro de los triángulos obligaría a "y" y a "z" a tener el mismo color que "x", pero entonces, como "y" y "z" están a una distancia unitaria entre sí, no se tendría una coloración adecuada del grafo de distancia unitaria del plano. Por lo tanto, se necesitan al menos cuatro colores para colorear este grafo y el plano que lo contiene. Un límite inferior alternativo en forma de un grafo de distancia unitaria de cuatro colores y diez vértices, el grafo de Golomb, fue descubierto aproximadamente al mismo tiempo por Solomon W. Golomb.^[4]​

El límite inferior se elevó a cinco en 2018, cuando el científico informático y biogerontologista Aubrey de Grey encontró un grafo de distancia unitaria de 1581 vértices, no coloreable con 4 colores. La prueba estaba asistida por computadora.^[5]​ El matemático Gil Kalai y el científico informático Scott Aaronson publicaron una discusión del hallazgo de De Grey, con Aaronson informando verificaciones independientes del resultado de De Grey usando SAT solver. Kalai vinculó publicaciones adicionales de Jordan Ellenberg y de Noam Elkies, con Elkies y (por separado) de Grey proponiendo un proyecto Polymath para encontrar grafos de distancia unitaria no coloreables con 4 colores con menos vértices que el de la construcción de De Grey.^[6]​ A partir de 2021, el grafo de distancia unitaria conocido más pequeño con número cromático 5 tiene 509 vértices.^[7]​ La página del proyecto Polymath, Polymath (2018), contiene más investigaciones, citas de medios y datos de verificación.

El límite superior de siete para el número cromático se deriva de la existencia de un teselado del plano formado por hexágonos regulares, con un diámetro ligeramente inferior a uno, a los que se les pueden asignar siete colores en un patrón repetitivo para formar una coloración de siete colores del plano. Según Soifer (2008), este límite superior fue observado por primera vez por John R. Isbell.

El problema puede extenderse fácilmente a dimensiones superiores. Hallar el número cromático del espacio tridimensional es un problema particularmente interesante. Al igual que con la versión en el plano, la respuesta se desconoce, pero se ha demostrado que es al menos 6 y como máximo 15.^[8]​

En el caso n-dimensional del problema, una cota superior sencilla para el número cromático requerido, obtenida al teselar cubos n-dimensionales, es ${\displaystyle \lfloor 2+{\sqrt {n}}\rfloor ^{n}}$ . Una cota inferior para los símplex es ${\displaystyle n+1}$ . Para ${\displaystyle n>1}$ , se dispone de una cota inferior para ${\displaystyle n+2}$  mediante una generalización del huso de Moser: un par de objetos (cada uno con dos símplex pegados en una faceta) unidos por un punto y una línea en el otro lado. Frankl y Wilson demostraron una cota inferior exponencial en 1981.^[9]​.

También se pueden considerar coloraciones del plano en las que los conjuntos de puntos de cada color están restringidos a conjuntos de un tipo particular.^[10]​ Estas restricciones pueden provocar un aumento en el número de colores requerido, ya que impiden que ciertas coloraciones se consideren aceptables. Por ejemplo, si la coloración del plano consta de regiones delimitadas por curvas, se requieren al menos seis colores.^[11]​

• Teorema de los cuatro colores

• O'Rourke, Joseph, «Problem 57: Chromatic Number of the Plane», The Open Problems Project .
• Mohar, Bojan (2001), The chromatic number of the Unit Distance Graph .
• Kalai, Gil (2018), Coloring Problems for Arrangements of Circles (and Pseudocircles) .
• Grime, James (27 de febrero de 2019), «A Colorful Unsolved Problem», Numberphile, archivado desde el original el 21 de diciembre de 2021 .