χ-limitado

En teoría de grafos , una familia de grafos acotada es aquella para la que existe alguna función tal que, para cada entero, los grafos en con ( número de clique ) pueden colorearse con como máximo colores. La función se denomina función de acotación 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 acotado se basa en el hecho de que el número cromático de un grafo se denota comúnmente como . 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 grafos esté acotada. Como demostraron Descartes (1947), Zykov (1949) y Mycielski (1955), existen grafos sin triángulos de número cromático arbitrariamente grande, ^{[3] [4] [5]} por lo que para estos grafos no es posible definir un valor finito de . Por lo 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 específicas

Toda clase de grafos de números cromáticos acotados está (trivialmente) acotada, con un valor igual al límite del número cromático. Esto incluye, por ejemplo, los grafos planares , los grafos bipartitos y los grafos de degeneración acotada . Complementariamente, los grafos en los que el número de independencia está acotado también están acotados, ya que el teorema de Ramsey implica que tienen camarillas grandes. ${\displaystyle \chi }$ ${\displaystyle f(t)}$ ${\displaystyle \chi }$

El teorema de Vizing puede interpretarse como que los grafos lineales están acotados, con . ^{[7] [8]} Los grafos sin garras en general también están acotados con . Esto se puede ver usando el teorema de Ramsey para mostrar que, en estos grafos, un vértice con muchos vecinos debe ser parte de una camarilla grande. Este límite es casi estricto en el peor de los casos, pero los grafos sin garras conectados 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}$
• Los gráficos de boxicidad dos ^[9] , que son los gráficos de intersección de rectángulos paralelos al eje, con ( notación O mayúscula ) ^[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]
• Los gráficos polígono-círculo , con ${\displaystyle f(t)=2^{t}}$
• Los gráficos circulares , con ^[13] y (generalizando los gráficos circulares) los "gráficos de cadena externa", gráficos de intersección de curvas acotadas en el plano que tocan todas la cara no acotada 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 cadena externa 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]
• Los gráficos de intersección de curvas que cruzan una curva fija entre 1 y tiempos ^[16] ${\displaystyle n\in \mathbb {N} }$
• Los grafos libres de agujeros pares , con , ya que cada uno de estos grafos tiene un vértice cuyo vecindario 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 cadenas externas son todos casos especiales de gráficos de cadenas , los gráficos de cadenas en sí mismos no están acotados. Incluyen como caso especial los gráficos de intersección de segmentos de línea , que tampoco están acotados. ^[6] ${\displaystyle \chi }$ ${\displaystyle \chi }$

Problemas sin resolver

Problema sin resolver en matemáticas :

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

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

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

Una clase de grafos acotada es polinómicamente acotada si tiene una función de enlace que crece como máximo polinómicamente en función de . Como cada grafo de vértice contiene un conjunto independiente con cardinalidad al menos , todas las clases acotadas polinómicamente tienen la propiedad de Erdős–Hajnal . Otro problema sobre la acotación fue planteado por Louis Esperet, quien preguntó si cada clase hereditaria de grafos que está acotada también está acotada polinómicamente. ^[8] Un fuerte contraejemplo a la conjetura de Esperet fue anunciado en 2022 por Briański, Davies y Walczak, quienes demostraron que existen clases hereditarias acotadas cuya función puede elegirse arbitrariamente siempre que crezca más rápidamente que un cierto 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 grafos perfectos" (PDF) , Actas de la Conferencia Internacional sobre Análisis Combinatorio y sus Aplicaciones (Pokrzywna, 1985), Zastosowania Matematyki , 19 (3–4): 413–441 (1988), MR  0951359
2. Scott, Alex; Seymour, Paul (2020), "Un estudio de la acotación", Journal of Graph Theory , 95 (3): 473–504, MR  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  0035428Traducido al inglés en Amer. Math. Soc. Translation , 1952, MR 0051516. Según cita 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, Maria ; 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), "Límite de Vizing para el número cromático en algunas clases de grafos", Graphs and Combinatorics , 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), "Coloración y peso máximo de un conjunto independiente de rectángulos", arXiv : 2007.07880 [cs.CG]
11. Dvořák, Zdeněk; Král', Daniel (2012), "Las clases de grafos con descomposiciones de rango pequeño están acotadas", European Journal of Combinatorics , 33 (4): 679–683, arXiv : 1107.2161 , doi :10.1016/j.ejc.2011.12.005, MR  3350076, S2CID  5530520 ${\displaystyle \chi }$
12. Kim, Seog-Jin; Kostochka, Alexandr; Nakprasit, Kittikorn (2004), "Sobre el número cromático de gráficos 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 American Mathematical Society , 150 (12): 5121–5135, arXiv : 2107.03585 , doi :10.1090/proc/16044
14. Rok, Alexandre; Walczak, Bartosz (2014), "Los grafos de cadenas 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, Alexandre; Walczak, Bartosz (2019), "Los gráficos de cadenas externas están acotados por χ", SIAM Journal on Discrete Mathematics , 33 (4): 2181–2199, arXiv : 1312.1559 , doi :10.1137/17M1157374, S2CID  9474387
16. Rok, Alexandre; Walczak, Bartosz (2019), "Coloración de curvas que cruzan una curva fija", Geometría discreta y computacional , 61 (4): 830–851, arXiv : 1512.06112 , doi : 10.1007/s00454-018-0031-z , S2CID  124706442
17. Chudnovsky, Maria ; Seymour, Paul (2023), "Los grafos sin agujeros pares aún tienen vértices bisimpliciales", Journal of Combinatorial Theory, Serie B , 161 : 331–381, arXiv : 1909.10967 , doi :10.1016/j.jctb.2023.02.009, MR  4568110
18. Kierstead, HA; Penrice, SG (1994), "Los árboles de radio dos especifican 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 polinomial 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 el Chi