Conjetura de Gyárfás-Sumner

Problema no resuelto en matemáticas :

¿Prohibir tanto un árbol como una camarilla como subgrafos inducidos produce gráficos 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 gráfico completo , los gráficos sin subgrafos ni como inducidos pueden colorearse adecuadamente utilizando solo un número constante de colores. De manera equivalente, pregunta si los gráficos libres están acotados . ^[1] Lleva el nombre de András Gyárfás y David Sumner , quienes lo formularon de forma independiente en 1975 y 1981 respectivamente. ^{[2] [3]} Aún no se ha demostrado. ^[4] ${\displaystyle T}$ ${\displaystyle K}$ ${\displaystyle T}$ ${\displaystyle K}$ ${\displaystyle T}$ ${\displaystyle \chi }$

En esta conjetura, no es posible sustituirla por una gráfica con ciclos. Como han demostrado Paul Erdős y András Hajnal , existen gráficos con un número cromático arbitrariamente grande y, al mismo tiempo, una circunferencia arbitrariamente grande . ^[5] Usando estos gráficos, se pueden obtener gráficos que evitan cualquier elección fija de un gráfico cíclico y una camarilla (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 cierta para ciertas elecciones especiales de , incluidos 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 gráficos de números cromáticos grandes", 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, SEÑOR  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, Amsterdam: Holanda Septentrional, págs. 801–816, MR  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, María ; Seymour, Paul (2014), "Ampliació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 gráficos perfectos", 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
7. Kierstead, HA; Penrice, SG (1994), "El radio de dos árboles especifica clases acotadas 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 delimitados por chi, Open Problem Garden