Conjetura de Albertson

Relación entre la coloración de gráficos y los cruces

Problema sin resolver en matemáticas :

¿ Los gráficos completos tienen el menor número de cruces posible entre gráficos con el mismo número cromático ?

(más problemas sin resolver en matemáticas)

El gráfico completo dibujado con tres cruces, el número de cruces más pequeño de cualquier gráfico que requiere seis colores. ${\displaystyle K_{6}}$

En matemáticas combinatorias , la conjetura de Albertson es una relación no probada entre el número de cruces y el número cromático de un grafo . Recibe su nombre de Michael O. Albertson, profesor del Smith College , quien la enunció como conjetura en 2007; ^[1] es una de sus muchas conjeturas en la teoría de coloración de grafos . ^[2] La conjetura establece que, entre todos los grafos que requieren colores, el grafo completo es el que tiene el número de cruces más pequeño. De manera equivalente, si un grafo se puede dibujar con menos cruces que , entonces, según la conjetura, se puede colorear con menos de colores. ${\displaystyle n}$ ${\displaystyle K_{n}}$ ${\displaystyle K_{n}}$ ${\displaystyle n}$

Una fórmula conjeturada para el número mínimo de cruces

Es sencillo demostrar que los grafos con número de cruces acotado tienen número cromático acotado: se pueden asignar colores distintos a los puntos finales de todos los bordes que se cruzan y luego aplicar 4 colores al grafo planar restante . La conjetura de Albertson reemplaza esta relación cualitativa entre el número de cruces y la coloración por una relación cuantitativa más precisa. Específicamente, una conjetura diferente de Richard K. Guy  (1972) establece que el número de cruces del grafo completo es ${\displaystyle K_{n}}$

${\displaystyle {\textrm {cr}}(K_{n})={\frac {1}{4}}{\biggl \lfloor }{\frac {n}{2}}{\biggr \rfloor }\left\lfloor {\frac {n-1}{2}}\right\rfloor \left\lfloor {\frac {n-2}{2}}\right\rfloor \left\lfloor {\frac {n-3}{2}}\right\rfloor .}$

Se sabe cómo dibujar grafos completos con esta cantidad de cruces, colocando los vértices en dos círculos concéntricos; lo que se desconoce es si existe un dibujo mejor con menos cruces. Por lo tanto, una formulación reforzada de la conjetura de Albertson es que todo grafo -cromático tiene un número de cruces al menos tan grande como el lado derecho de esta fórmula. ^[3] Esta conjetura reforzada sería verdadera si y solo si tanto la conjetura de Guy como la conjetura de Albertson son verdaderas. ${\displaystyle n}$

Límites asintóticos

Una forma más débil de la conjetura, probada por M. Schaefer, ^[3] establece que todo grafo con número cromático tiene número de cruce (usando la notación omega grande ), o equivalentemente que todo grafo con número de cruce tiene número cromático . Albertson, Cranston y Fox (2009) publicaron una prueba simple de estos límites, combinando el hecho de que todo grafo minimal -cromático tiene grado mínimo al menos  (porque de lo contrario la coloración voraz usaría menos colores) junto con la desigualdad del número de cruce según la cual todo grafo con tiene número de cruce . Usando el mismo razonamiento, muestran que un contraejemplo a la conjetura de Albertson para el número cromático (si existe) debe tener menos de vértices. ${\displaystyle n}$ ${\displaystyle \Omega (n^{4})}$ ${\displaystyle k}$ ${\displaystyle O(k^{1/4})}$ ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle G=(V,E)}$ ${\displaystyle |E|/|V|\geq 4}$ ${\displaystyle \Omega (|E|^{3}/|V|^{2})}$ ${\displaystyle n}$ ${\displaystyle 4n}$

Casos especiales

La conjetura de Albertson es vacuamente cierta para . En estos casos, tiene número de cruces cero, por lo que la conjetura solo establece que los grafos -cromáticos tienen número de cruces mayor o igual a cero, algo que es cierto para todos los grafos. El caso de la conjetura de Albertson es equivalente al teorema de los cuatro colores , que cualquier grafo planar puede colorearse con cuatro o menos colores, ya que los únicos grafos que requieren menos cruces que el cruce de son los grafos planares, y la conjetura implica que todos estos deberían ser como máximo 4-cromáticos. Gracias a los esfuerzos de varios grupos de autores, ahora se sabe que la conjetura es válida para todos los . ^[4] Para cada entero , Luiz y Richter presentaron una familia de grafos -color-críticos que no contienen una subdivisión del grafo completo pero tienen número de cruces al menos igual a . ^[5] ${\displaystyle n\leq 4}$ ${\displaystyle K_{n}}$ ${\displaystyle n}$ ${\displaystyle n=5}$ ${\displaystyle K_{5}}$ ${\displaystyle n\leq 18}$ ${\displaystyle c\geq 6}$ ${\displaystyle (c+1)}$ ${\displaystyle K_{c+1}}$ ${\displaystyle K_{c+1}}$

Conjeturas relacionadas

También existe una conexión con la conjetura de Hadwiger , un importante problema abierto en combinatoria que concierne a la relación entre el número cromático y la existencia de grandes camarillas como menores en un grafo. ^[6] Una variante de la conjetura de Hadwiger, enunciada por György Hajós , es que cada grafo -cromático contiene una subdivisión de ; si esto fuera cierto, se seguiría la conjetura de Albertson, porque el número de cruces de todo el grafo es al menos tan grande como el número de cruces de cualquiera de sus subdivisiones. Sin embargo, ahora se conocen contraejemplos de la conjetura de Hajós, ^[7] por lo que esta conexión no proporciona una vía para la prueba de la conjetura de Albertson. ${\displaystyle n}$ ${\displaystyle K_{n}}$

Notas

1. Según Albertson, Cranston y Fox (2009), la conjetura fue hecha por Albertson en una sesión especial de la Sociedad Matemática Americana en Chicago, celebrada en octubre de 2007.
2. Hutchinson, Joan P. (19 de junio de 2009), En memoria de Michael O. Albertson, 1946-2009: una colección de sus conjeturas y preguntas destacadas en teoría de grafos (PDF) , Grupo de actividad SIAM sobre matemáticas discretas.
3. Albertson, Cranston y Fox (2009).
4. Oporowski y Zhao (2009); Albertson, Cranston y Fox (2009); Barát y Tóth (2010); Ackerman (2019).
5. Luiz y Richter (2014).
6. Barát y Tóth (2010).
7. Catlín (1979); Erdős y Fajtlowicz (1981).

Referencias

• Ackerman, Eyal (2019), "Sobre gráficos topológicos con un máximo de cuatro cruces por arista", Computational Geometry , 85 : 101574, 31, arXiv : 1509.01932 , doi : 10.1016/j.comgeo.2019.101574, MR  4010251, S2CID  16847443
• Albertson, Michael O.; Cranston, Daniel W.; Fox, Jacob (2009), "Coloraciones, cruces y camarillas" (PDF) , Electronic Journal of Combinatorics , 16 : R45, arXiv : 1006.3783 , Bibcode :2010arXiv1006.3783A, doi :10.37236/134, S2CID  8837711.
• Barát, János; Tóth, Géza (2010), "Hacia la conjetura de Albertson", Electronic Journal of Combinatorics , 17 (1): R73, arXiv : 0909.0413 , Bibcode :2009arXiv0909.0413B, doi :10.37236/345, S2CID  14640959.
• Catlin, PA (1979), "Conjetura de coloración de grafos de Hajós: variaciones y contraejemplos", Journal of Combinatorial Theory, Serie B , 26 (2): 268–274, doi : 10.1016/0095-8956(79)90062-5.
• Erdős, Paul ; Fajtlowicz, Siemion (1981), "Sobre la conjetura de Hajós", Combinatorica , 1 (2): 141–143, doi :10.1007/BF02579269, S2CID  1266711.
• Guy, Richard K. (1972), "Números cruzados de grafos", en Alavi, Y .; Lick, DR; White, AT (eds.), Graph Theory and Applications: Proceedings of the Conference at Western Michigan University, Kalamazoo, Michigan, 10-13 de mayo de 1972 , Nueva York: Springer-Verlag, págs. 111-124Como citan Albertson, Cranston y Fox (2009).
• Oporowski, B.; Zhao, D. (2009), "Coloración de gráficos con cruces", Discrete Mathematics , 309 (9): 2948–2951, arXiv : math/0501427 , doi :10.1016/j.disc.2008.07.040, S2CID  16497175.
• Luiz, Atílio; Richter, Bruce (2014), "Observaciones sobre una conjetura de Barát y Tóth", Revista Electrónica de Combinatoria , 21 (1): P1.57, doi : 10.37236/3396.