Algunos antecedentes:
Sé que para gráficos finitos, si un gráfico no tiene un ciclo impar (es decir, es bipartito), puede ser -de colores. De manera similar, un gráfico sin o es plano, por lo que puede ser -de colores.
Esta pregunta analiza una aplicación de "ciclo no impar" a gráficos infinitos (específicamente, los gráficos de distancia de unidad racional y real). Entiendo por qué un ciclo impar implicaría que el gráfico de distancia unitaria real no es -colorable (ni siquiera es -colorable), y por qué "sin ciclo impar" debería implicar -colorabilidad de un gráfico infinito (si intentas -coloréalo, nunca te encontrarás con ningún problema), pero ¿es esto un argumento formal?
Además, supongamos que tengo un gráfico finito sin un . Esto significa que no puede tener un o un , entonces es plano y -de colores. ¿Es necesario el concepto de planaridad para estos -argumentos de colorabilidad, y ¿eso existe para gráficos infinitos incontables? De cualquier manera, me gustaría usar la misma lógica para un gráfico infinito numerable (digamos, el gráfico de unidad de distancia en ) o un gráfico incontablemente infinito (como el gráfico de unidad de distancia en , que de hecho está libre de ). ¿Sería esta una aplicación correcta de esos dos teoremas? (Estoy especialmente preocupado por la -teorema del color; dado que terminó en una verificación de caso finito, dudo que se mantenga para gráficos infinitos)
Nunca he trabajado con gráficos infinitos, así que no estoy muy seguro de por dónde empezar con ninguno de estos. Cualquier cosa sobre esto que me señale en la dirección correcta sería muy apreciada.
El punto es que un -la coloración de un gráfico infinito también es un -coloreado de todos sus subgrafos. Así que un gráfico finito que no es -colorable no puede ocurrir como un subgrafo de un -gráfico infinito coloreable.
Por otro lado, el teorema de De Bruijn-Erdős dice que un grafo cuyos subgrafos finitos son todos -Colorable es -de colores.
Carl Schildkraut
Gregorio J. Puleo
Carl Schildkraut