El teorema de cuatro colores (4CT) establece que cada gráfico plano tiene cuatro colores. Hay dos pruebas dadas por [Appel, Haken 1976] y [Robertson, Sanders, Seymour, Thomas 1997]. Ambas pruebas son asistidas por computadora y bastante intimidantes.
Hay varias conjeturas en la teoría de grafos que implican 4CT. La resolución de estas conjeturas probablemente requiera una mejor comprensión de las pruebas de 4CT. Aquí hay una de estas conjeturas:
Conjetura : Sea un gráfico plano, sea un conjunto de colores una involución libre de punto fijo. Deje ser tal que
- para todos y
- si entonces para todos , para todos los .
Entonces existe una -Coloreado de la gráfica .
Si conoce tales conjeturas que implican 4CT, enumere una en cada respuesta. No pude encontrar una lista completa de tales conjeturas.
graph-theory
co.combinatorics
big-list
graph-colouring
Shiva Kintali
fuente
fuente
Respuestas:
4CT es equivalente a:
Se presenta un equivalente algebraico del teorema de cuatro colores. El equivalente es la afirmación de no pertenencia a una familia de polinomios en una familia de ideales polinomiales sobre un campo finito particular .[6]
fuente
George Gonthier de Microsoft Research Cambridge ha realizado otra verificación mecánica del teorema de 4 colores . La diferencia con su prueba es que todo el teorema se ha establecido y verificado mecánicamente utilizando el asistente de pruebas Coq, mientras que las otras pruebas contienen solo el cálculo del núcleo escrito en lenguaje ensamblador y C, y por lo tanto tienen el riesgo de tener errores. La prueba de Gonthier cubre tanto los aspectos de cálculo como los lógicos en solo 60,000 líneas de Coq.
fuente
He hablado sobre esto en mi blog y nuestra idea es: por ejemplo, la condición de Tait puede debilitarse porque hay una coloración que tiene como máximo o (n) errores. Ver aquí: http://rjlipton.wordpress.com/2009/04/24/the-four-color-theorem/
fuente
Mira T. Saaty, Trece variaciones coloridas en la conjetura de 4 colores de Guthrie, American Math. Mensual, 79 (1972) 2-43 para muchos ejemplos.
Además, en el libro de David Barnette Map Coloring, Polyhedra, and the Four-Color Problem, MAA, Dolciani Series, Volumen 8, 1983 se dan muchos ejemplos. Un resultado particularmente interesante en el libro de Barnete es: si siempre es posible truncar los vértices de un poliedro convexo para producir un poliedro convexo de 3 vales de modo que el número de lados de cada cara sea múltiplo de tres, implica que verdad de la conjetura de cuatro colores.
fuente
La conjetura de Hadwiger .
fuente
En el artículo Absolute Planar Retracts y Four Color Conjecture , Pavol Hell probó varias formulaciones equivalentes para el 4CT. Uno de ellos dice lo siguiente:
fuente
Cada gráfico plano cúbico sin puente es coloreable por 3 bordes. (Esto es equivalente a 4CT, debido a Tait).
fuente
El artículo de Dror Bar-Natan "Lie Algebras and the Four Color Theorem" (Combinatorica 17-1 (1997) 43-52, última actualización en octubre de 1999, arXiv: q-alg / 9606016 ) contiene una atractiva declaración sobre álgebras de Lie que es equivalente a El teorema de los cuatro colores. Las nociones que aparecen en la declaración también aparecen en la teoría de los invariantes de nudos de tipo finito (invariantes de Vassiliev) y 3-múltiples.
fuente
La Proposición 2.4 en este documento http://www.sciencedirect.com/science/article/pii/0012365X9500109A# da otra formulación para el 4CT.
fuente
Vale la pena leer la descripción de alto nivel de la prueba automatizada de Gonthier, si está buscando más información.
Yuri Matiyasevich estudió varias reformulaciones probabilísticas del Teorema de los cuatro colores, que implican correlaciones positivas entre dos nociones de similitud entre coloraciones. Sus pruebas de equivalencia se basan en un polinomio gráfico asociado, que proporciona otro puntero probable a conjeturas que implican el teorema.
fuente
Acabo de leer en un artículo de Chalopin y Gonçalves (STOC '09) la siguiente conjetura de West:
Dado que los segmentos paralelos forman un conjunto independiente en dicha representación, esta conjetura implica el 4CT, pero quizás sea aún más fuerte.
La referencia: Oeste, problemas abiertos . SIAM J Discrete Math Newsletter, 2 (1): 10-12, 1991.
fuente
Un snark es un gráfico cúbico sin puente conectado que no se puede colorear con 3 bordes. Después de wikipedia, la conjetura snark , que generaliza el 4CT, es la siguiente:
Nuevamente, según Wikipedia, una prueba de esta conjetura fue anunciada en 2001 por Robertson, Sanders, Seymour y Thomas.
fuente
"El etiquetado facial de los gráficos planos máximos" es el título de mi artículo anterior que se publicó recientemente en el que he transformado 4 colores de gráficos planos máximos en consistencia del etiquetado facial. El enlace al documento es http://www.math.nsysu.edu.tw/~amen/2011/091021-3.pdf
fuente
Como
LH Kauffman, Reformulación del teorema del color del mapa , Matemática discreta 302 (2005) 145–172
señala, el Principio de Primalidad debido a G. Spencer-Brown, así como la conjetura de Eliahou-Kryuchkov son reformulaciones equivalentes de la FCT.
fuente
El documento de Garry Bowlin y Matthew G. Brin "Colorear gráficos planos a través de caminos coloreados en la Associahedra", revisado por última vez el 12 de mayo de 2013, arXiv: 1301.3984 math.CO contiene la siguiente conjetura en la página 26:
Se afirma que la conjetura 6.4 que sigue a proposiciones y teoremas anteriores en el documento es equivalente a 4CT.
fuente
A k -flow en un grafo no dirigido G es un grafo dirigido derivados mediante la sustitución de cada borde en G con un arco y asignándole un número entero entre -k y k , exclusivo, de tal manera que, para cada vértice en G, la suma de los números enteros asignado a los arcos que apuntan a ese vértice es igual a la suma de los enteros asignados a los arcos que apuntan. Un flujo K de NWZ (en ninguna parte cero) es un flujo k en el que no se ha asignado ningún arco al número 0.
Para cualquier gráfico plano G , el dual de G es el gráfico que contiene un vértice para cada cara en una incrustación plana de G , y dos vértices en un doble comparten un borde que los conecta para cada borde que las caras correspondientes en G comparten entre ellos en sus límites De acuerdo con el teorema de dualidad Flow-Coloring de Tutte, un gráfico plano sin istmo (es decir, un borde cuya eliminación aumentaría el número de componentes) tiene un flujo k NWZ si y solo si su dual es k- colourable. En otras palabras, un gráfico plano es 4-colourable si y solo si su dual tiene un flujo NWZ 4.
Tenga en cuenta que 4CT requiere que el gráfico plano en cuestión no tenga bucles (bordes que conectan cualquier vértice consigo mismo) porque cualquier gráfico con un bucle no puede ser coloreado con ningún conjunto de colores, ya que cualquier vértice con un bucle sería adyacente a un vértice del mismo color, independientemente de su color.
fuente
Estoy trabajando en esto:
Si puede probar el teorema de los mapas rectangulares, que son mapas hechos de hojas de papel superpuestas, también ha demostrado el 4ct. Además, solo se pueden considerar en la búsqueda mapas con caras que tengan los 5 bordes o más.
Ver http://4coloring.wordpress.com/ para más detalles.
fuente