Generalizaciones del teorema de los cuatro colores.

Question

El cuatro de color teorema afirma que cada plano gráfico se puede correctamente de color por cuatro colores.

El propósito de esta pregunta es recoger las generalizaciones, las variaciones y los reforzamientos de los cuatro colores teorema con una descripción de su estado.

(Motivado por un comentario de rupeixu a un reciente post en mi blog la presentación de una pregunta por Abby Thompson respecto a una generalización natural de la 4CT.) Relacionadas con la pregunta:Generalizaciones de Grafos Planares .

Answer 1

Uno de los más importantes generalizaciones del teorema de los cuatro colores es Hadwiger de la conjetura. El Hadwiger conjetura afirma que un gráfico sin un $K_{r+1}$ menor es $r$-engañosa. Hay una mayor generalización llamado la Débil Hadwiger Conjetura.

Se sabe que el Hadwiger conjetura es falsa para gráficos con infinito cromática (número de considerar la inconexión de la unión de $K_n$ donde $n\in\mathbb{N}$), mientras que los Débiles Hadwiger conjetura es verdadera para los gráficos (ver este artículo).

Una pregunta interesante es si la Débil Hadwiger conjetura implica la Hadwiger conjetura para grafos finitos.

Answer 2

La coloración de las dimensiones superiores de la bola de envases.

Una bola de embalaje es una colección de bolas con distintos interiores. La tangencia gráfica de una pelota de embalaje toma las bolas como vértices y conecta dos vértices si y sólo si son tangentes. Grafos planares son los de tangencia gráficos de 2 dimensiones disco de envases. Así que la siguiente es una generalización de cuatro colores teorema.

Pregunta: ¿cuál es el máximo cromática número $\chi_d$ para la tangencia gráfica de una pelota de embalaje en la dimensión $d$?

Yo creo que todo el mundo puede probar que $\chi_d\le\kappa_d+1$ donde $\kappa_d$ es el beso número. La pregunta fue hecha por Bagchi y Datta (2012) quien le dio el trivial límite inferior $\chi_d\ge d+2$.

Hasta donde yo sé, Maehara (2007) primer ataque el problema de la dimensión $3$. Su construcción para el límite inferior utiliza Moser eje. Se generaliza a dimensiones superiores y da $\chi_d\ge d+3$.

El problema también ha sido preguntado sobre MO. Un resultado es una respuesta de Cantwell. Utiliza la mitad de los cubos. Se puede generalizar a dimensiones superiores por un resultado de Liniail, Mishulam y Tarsi (1988) y da $\chi_d\ge d+4$ para infinidad de $d$.

Por lo que el estado actual es: $d+4\le\chi_d\le\kappa_d+1$. Hay una gran diferencia entre ellos.

---

actualización: acabo de mejorar el límite inferior por la construcción de una unidad de la bola de embalaje en la dimensión $q^3-q^2+q$ con cromática número $q^3+1$ donde $q$ es una fuente primaria de energía. Hay muchas otras bola de envases con alta cromática número, consulte esta respuesta. La brecha es todavía muy grande.

Answer 3

Aquí son dos:

Recordemos que el teorema de los cuatro colores es equivalente a la afirmación de que bridgeless cúbicos grafos planares son tres-edge-colourable.

Hay Tutte tres-edge-coloración de la conjetura de que todo cúbicos bridgeless gráfico no contiene el gráfico de Petersen como un menor de edad es de 3-borde-colourable. Este es un teorema de ahora.

Una (todavía abierto) la generalización de este es Tutte 4-flujo de la conjetura de que cada bridgeless gráfico no Petersen menor tiene nada-cero 4-flujo.

El otro es una conjetura de Seymour acerca de $d$-regular planar (multi-)gráficos. Esto nos dice que todos los $d$-regular plana gráfico que cumpla los naturales de la corte condición (para todos los pares de cardinalidad subconjunto $X$ de los vértices hay, al menos, $d$ bordes entre las $X$ y el complemento) es $d$-edge-colourable. Este todavía está abierta en general, pero conocido por los valores de $d \leq 8$ (ver aquí).

Answer 4

El polinomio cromático de cualquier gráfico plano no tiene raíces reales que sean mayores o iguales a cuatro.

Tenga en cuenta que el teorema de los cuatro colores dice que 4 no puede ser una raíz, y es bien sabido que las raíces no pueden ser números reales mayores o iguales a 5.

Answer 5

Kronheimer y Mrowka definido recientemente un instanton invariantes de la incrustados trivalente gráficos (webs) en $\mathbb{R}^3$. Esto puede ser considerado como (más o menos) contar el número de representaciones del grupo fundamental de la dotación de la gráfica de $SO(3)$ tal que el meridiano de cada borde es enviado a una involución. Se conjetura que para planar webs de sus invariantes da el número de Tait colorantes (es fácil ver que un Tait para colorear da una representación de este tipo para el Klein cuatro grupo). Ellos demuestran que esto es cierto para Euleriano plana trivalente gráficos, entre otros. Ellos muestran que sus invariantes es siempre distinto de cero, y por lo tanto, esta conjetura implica el teorema de los cuatro colores. Asimismo, se dan varios refinamientos de esta conjetura en este papel y una secuela. Ver también en este blog-post.