χ-limitado

En teoría de grafos , una familia acotada de gráficos es aquella para la cual existe alguna función tal que, para cada número entero, los gráficos con ( número de camarilla ) se pueden colorear con la mayoría de los colores. La función se llama función vinculante para . Estos conceptos y sus notaciones fueron formulados por András Gyárfás . ^[1] El uso de la letra griega chi en el término -limitado se basa en el hecho de que comúnmente se denota el número cromático de un gráfico . Se puede encontrar una descripción general del área en una encuesta de Alex Scott y Paul Seymour . ^[2] ${\displaystyle \chi }$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle f}$ ${\displaystyle t}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle t=\omega (G)}$ ${\displaystyle f(t)}$ ${\displaystyle f(t)}$ ${\displaystyle \chi }$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle \chi }$ ${\displaystyle G}$ ${\displaystyle \chi (G)}$

No trivialidad

No es cierto que la familia de todos los gráficos esté acotada. Como demostraron Descartes (1947), Zykov (1949) y Mycielski (1955), existen gráficas sin triángulos de números cromáticos arbitrariamente grandes, ^{[3] [4] [5],} por lo que para estas gráficas no es posible definir una gráfica finita. valor de . Por tanto, la acotación es un concepto no trivial, verdadero para algunas familias de grafos y falso para otras. ^[6] ${\displaystyle \chi }$ ${\displaystyle f(2)}$ ${\displaystyle \chi }$

Clases especificas

Cada clase de gráficos de número cromático acotado está (trivialmente) acotado, con igual al límite del número cromático. Esto incluye, por ejemplo, las gráficas planas , las gráficas bipartitas y las gráficas de degeneración acotada . Complementariamente, las gráficas en las que el número de independencia está acotado también lo están, ya que el teorema de Ramsey implica que tienen grandes camarillas. ${\displaystyle \chi }$ ${\displaystyle f(t)}$ ${\displaystyle \chi }$

Se puede interpretar que el teorema de Vizing establece que las gráficas lineales están acotadas, con . ^{[7] [8]} Los gráficos sin garras en general también están delimitados con . Esto se puede ver utilizando el teorema de Ramsey para demostrar que, en estos gráficos, un vértice con muchos vecinos debe ser parte de una camarilla grande. Este límite es casi estrecho en el peor de los casos, pero los gráficos conectados sin garras que incluyen tres vértices mutuamente no adyacentes tienen un número cromático aún menor, . ^[7] ${\displaystyle \chi }$ ${\displaystyle f(t)=t+1}$ ${\displaystyle \chi }$ ${\displaystyle f(t)\leq t^{2}}$ ${\displaystyle f(t)=2t}$

Otras familias de gráficos acotados incluyen: ${\displaystyle \chi }$

• Los gráficos perfectos , con ${\displaystyle f(t)=t}$
• Las gráficas de boxicidad dos ^[9] , que son las gráficas de intersección de rectángulos paralelos al eje, con ( notación O grande ) ^[10] ${\displaystyle f(t)\in O(t\log(t))}$
• Los gráficos de ancho de camarilla acotado ^[11]
• Los gráficos de intersección de copias escaladas y trasladadas de cualquier forma convexa compacta en el plano ^[12]
• Las gráficas de polígono-círculo , con ${\displaystyle f(t)=2^{t}}$
• Los gráficos circulares , con ^[13] y (generalizando gráficos circulares) los "gráficos de cuerdas externas", gráficos de intersección de curvas acotadas en el plano que tocan la cara ilimitada de la disposición de las curvas ^[14] ${\displaystyle f(t)=2t\log _{2}t+2\log _{2}\log _{2}t+10t}$
• El gráfico de cuerdas externas es un gráfico de intersección de curvas que se encuentran en un semiplano común y tienen un punto final en el límite de ese semiplano ^[15]
• Las gráficas de intersección de curvas que cruzan una curva fija entre 1 y veces ^[16] ${\displaystyle n\in \mathbb {N} }$
• Los gráficos libres de agujeros pares , con , ya que cada gráfico tiene un vértice cuya vecindad es la unión de dos camarillas ^[17] ${\displaystyle f(t)=2t}$

Sin embargo, aunque los gráficos de intersección de formas convexas, los gráficos circulares y los gráficos de cuerdas externas son casos especiales de los gráficos de cuerdas , los gráficos de cuerdas en sí no están acotados. Incluyen como caso especial las gráficas de intersección de segmentos de recta , que tampoco están acotadas. ^[6] ${\displaystyle \chi }$ ${\displaystyle \chi }$

Problemas no resueltos

Problema no resuelto en matemáticas :

¿Todas las clases de gráficos sin árboles están limitadas? ${\displaystyle \chi }$

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

Según la conjetura de Gyárfás-Sumner , para cada árbol , los gráficos que no contienen un subgrafo inducido están acotados. Por ejemplo, esto incluiría el caso de gráficos sin garras, ya que una garra es un tipo especial de árbol. Sin embargo, se sabe que la conjetura es cierta sólo para ciertos árboles especiales, incluidos los caminos ^[1] y los árboles de radio dos. ^[18] ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle \chi }$

Una clase de gráficos acotada está acotada polinomialmente si tiene una función vinculante que crece como máximo polinomialmente en función de . Como cada gráfico de vértice contiene un conjunto independiente con al menos cardinalidad , todas las clases acotadas polinómicamente tienen la propiedad de Erdős-Hajnal . Otro problema sobre la acotación lo planteó Louis Esperet, quien preguntó si toda clase hereditaria de grafos que está acotada también lo está polinomialmente. ^[8] Briański, Davies y Walczak anunciaron en 2022 un fuerte contraejemplo a la conjetura de Esperet, quienes demostraron que existen clases hereditarias acotadas cuya función puede elegirse arbitrariamente siempre que crezca más rápidamente que un determinado polinomio cúbico. ^[19] ${\displaystyle \chi }$ ${\displaystyle \chi }$ ${\displaystyle \chi }$ ${\displaystyle f(t)}$ ${\displaystyle t}$ ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle n/\chi (G)}$ ${\displaystyle \chi }$ ${\displaystyle \chi }$ ${\displaystyle \chi }$ ${\displaystyle \chi }$ ${\displaystyle \chi }$ ${\displaystyle f(t)}$

Referencias

1. Gyárfás, A. (1987), "Problemas del mundo que rodea a los gráficos perfectos" (PDF) , Actas de la Conferencia Internacional sobre Análisis Combinatorio y sus Aplicaciones (Pokrzywna, 1985), Zastosowania Matematyki , 19 (3–4): 413–441 (1988), SEÑOR  0951359
2. Scott, Álex; Seymour, Paul (2020), "Un estudio sobre la acotación", Journal of Graph Theory , 95 (3): 473–504, SEÑOR  4174126 ${\displaystyle \chi }$
3. Descartes, Blanche (1947), "Un problema de tres colores", Eureka , 21
4. Zykov, AA (1949), "О некоторых свойствах линейных комплексов" [Sobre algunas propiedades de los complejos lineales], Mat. Sbornik , Nueva Serie (en ruso), 24 (66): 163–188, SEÑOR  0035428. Traducido al inglés en Amer. Matemáticas. Soc. Traducción , 1952, MR 0051516. Citado por Pawlik et al. (2014)
5. Mycielski, Jan (1955), "Sur le coloriage des graphs", Colloq. Matemáticas. (en francés), 3 (2): 161–162, doi : 10.4064/cm-3-2-161-162 , SEÑOR  0069494
6. Pawlik, Arkadiusz; Kozik, Jakub; Krawczyk, Tomasz; Lasoń, Michał; Micek, Piotr; Trotón, William T .; Walczak, Bartosz (2014), "Gráficos de intersección sin triángulos de segmentos de línea con números cromáticos grandes", Journal of Combinatorial Theory, Serie B , 105 : 6–10, arXiv : 1209.1595 , doi : 10.1016/j.jctb.2013.11. 001, SEÑOR  3171778, S2CID  9705484
7. Chudnovsky, María ; Seymour, Paul (2010), "Gráficos sin garras VI. Coloración", Journal of Combinatorial Theory, Serie B , 100 (6): 560–572, doi : 10.1016/j.jctb.2010.04.005 , MR  2718677
8. Karthick, T.; Maffray, Frédéric (2016), "Visualización del límite del número cromático en algunas clases de gráficos", Gráficos y combinatoria , 32 (4): 1447–1460, doi :10.1007/s00373-015-1651-1, MR  3514976, S2CID  41279514
9. Asplund, E.; Grünbaum, B. (1960), "Sobre un problema de coloración", Mathematica Scandinavica , 8 : 181–188, doi : 10.7146/math.scand.a-10607 , MR  0144334
10. Chalermsook; Walczak (2020), "Conjunto de rectángulos independientes de color y peso máximo", arXiv : 2007.07880 [cs.CG]
11. Dvořák, Zdeněk; Král', Daniel (2012), "Las clases de gráficos con descomposiciones de rangos pequeños están acotadas", European Journal of Combinatorics , 33 (4): 679–683, arXiv : 1107.2161 , doi :10.1016/j.ejc.2011.12.005 , SEÑOR  3350076, S2CID  5530520 ${\displaystyle \chi }$
12. Kim, Seog-Jin; Kostochka, Alexandr; Nakprasit, Kittikorn (2004), "Sobre el número cromático de gráficas de intersección de conjuntos convexos en el plano", Electronic Journal of Combinatorics , 11 (1), R52, doi : 10.37236/1805 , MR  2097318
13. Davies, James (2022), "Límites mejorados para colorear gráficos circulares", Actas de la Sociedad Matemática Estadounidense , 150 (12): 5121–5135, arXiv : 2107.03585 , doi :10.1090/proc/16044
14. Rok, Alejandro; Walczak, Bartosz (2014), "Los gráficos de cuerdas externas están acotados", Actas del trigésimo simposio anual sobre geometría computacional (SoCG'14) , Nueva York: ACM, págs. 136-143, doi :10.1145/2582112.2582115, MR  3382292, S2CID  33362942 ${\displaystyle \chi }$
15. Rok, Alejandro; Walczak, Bartosz (2019), "Los gráficos de cuerdas externas están delimitados por χ", Revista SIAM de matemáticas discretas , 33 (4): 2181–2199, arXiv : 1312.1559 , doi : 10.1137/17M1157374, S2CID  9474387
16. Rok, Alejandro; Walczak, Bartosz (2019), "Colorear curvas que cruzan una curva fija", Geometría computacional y discreta , 61 (4): 830–851, arXiv : 1512.06112 , doi : 10.1007/s00454-018-0031-z , S2CID  124706442
17. Chudnovsky, María ; Seymour, Paul (2023), "Los gráficos sin agujeros pares todavía tienen vértices bisimpliciales", Journal of Combinatorial Theory, Serie B , 161 : 331–381, arXiv : 1909.10967 , doi : 10.1016/j.jctb.2023.02.009, Señor  4568110
18. Kierstead, HA; Penrice, SG (1994), "El radio de dos árboles especifica clases acotadas", Journal of Graph Theory , 18 (2): 119–129, doi :10.1002/jgt.3190180203, MR  1258244 ${\displaystyle \chi }$
19. Brianski, Marcin; Davies, James; Walczak, Bartosz (2023), "Separación de la acotación polinómica de la acotación", Combinatorica , arXiv : 2201.08814 , doi :10.1007/s00493-023-00054-3, S2CID  246476859 ${\displaystyle \chi }$ ${\displaystyle \chi }$

enlaces externos

• Jardín de problemas abiertos y delimitado por Chi