Conjetura de Gyárfás-Sumner

Problema sin resolver en matemáticas :

¿Prohibir tanto un árbol como una camarilla como subgrafos inducidos produce grafos de número cromático acotado?

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

En teoría de grafos , la conjetura de Gyárfás-Sumner pregunta si, para cada árbol y grafo completo , los grafos sin subgrafos inducidos ni como subgrafos pueden colorearse adecuadamente utilizando solo un número constante de colores. De manera equivalente, pregunta si los grafos libres están acotados . ^[1] Recibe su nombre en honor a András Gyárfás y David Sumner , quienes la formularon de forma independiente en 1975 y 1981 respectivamente. ^{[2] [3]} Sigue sin demostrarse. ^[4] ${\displaystyle T}$ ${\displaystyle K}$ ${\displaystyle T}$ ${\displaystyle K}$ ${\displaystyle T}$ ${\displaystyle \chi }$

En esta conjetura, no es posible reemplazar por un grafo con ciclos. Como Paul Erdős y András Hajnal han demostrado, existen grafos con un número cromático arbitrariamente grande y, al mismo tiempo, una circunferencia arbitrariamente grande . ^[5] Usando estos grafos, uno puede obtener grafos que evitan cualquier elección fija de un grafo cíclico y clique (de más de dos vértices) como subgrafos inducidos, y exceden cualquier límite fijo en el número cromático. ^[1] ${\displaystyle T}$

Se sabe que la conjetura es verdadera para ciertas elecciones especiales de , incluyendo caminos , ^[6] estrellas y árboles de radio dos. ^[7] También se sabe que, para cualquier árbol , los gráficos que no contienen ninguna subdivisión de están acotados. ^[1] ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle \chi }$

Referencias

1. Scott, AD (1997), "Árboles inducidos en grafos de gran número cromático", Journal of Graph Theory , 24 (4): 297–311, CiteSeerX  10.1.1.176.1458 , doi :10.1002/(SICI)1097-0118(199704)24:4<297::AID-JGT2>3.3.CO;2-X, MR  1437291
2. Gyárfás, A. (1975), "Sobre los números de cobertura de Ramsey", Conjuntos infinitos y finitos (Colloq., Keszthely, 1973; dedicado a P. Erdős en su 60 cumpleaños), vol. II , coloq. Matemáticas. Soc. János Bolyai, vol. 10, Ámsterdam: Holanda Septentrional, págs. 801–816, SEÑOR  0382051
3. Sumner, DP (1981), "Subárboles de un gráfico y el número cromático", La teoría y aplicaciones de los gráficos (Kalamazoo, Michigan, 1980) , Wiley, Nueva York, págs. 557–576, MR  0634555
4. Chudnovsky, Maria ; Seymour, Paul (2014), "Extensión de la conjetura de Gyárfás-Sumner", Journal of Combinatorial Theory , Serie B, 105 : 11–16, doi : 10.1016/j.jctb.2013.11.002 , MR  3171779
5. Erdős, P .; Hajnal, A. (1966), "Sobre el número cromático de gráficos y sistemas de conjuntos" (PDF) , Acta Mathematica Academiae Scientiarum Hungaricae , 17 (1–2): 61–99, doi : 10.1007/BF02020444 , MR  0193025
6. Gyárfás, A. (1987), "Problemas del mundo que rodea a los grafos perfectos", Actas de la Conferencia Internacional sobre Análisis Combinatorio y sus Aplicaciones (Pokrzywna, 1985), Zastosowania Matematyki , 19 (3–4): 413–441 (1988), MR  0951359
7. Kierstead, HA; Penrice, SG (1994), "Los árboles de radio dos especifican clases limitadas por χ", Journal of Graph Theory , 18 (2): 119–129, doi :10.1002/jgt.3190180203, MR  1258244

Enlaces externos

• Los gráficos con un árbol inducido prohibido están acotados por chi, Jardín de problemas abiertos