¿Prohibir tanto un árbol como una camarilla como subgrafos inducidos produce gráficos de número cromático acotado?
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 ninguno ni ya que los subgrafos inducidos se pueden colorear correctamente utilizando solo un número constante de colores. De manera equivalente, pregunta si el-Los gráficos libres son -limitado . [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] Sigue sin probarse. [4]
En esta conjetura, no es posible reemplazar por un gráfico 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]
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 una subdivisión de están -encerrado. [1]
Referencias
- ^ a b c Scott, AD (1997), "Árboles inducidos en gráficos de gran número cromático", Journal of Graph Theory , 24 (4): 297–311, doi : 10.1002 / (SICI) 1097-0118 (199704) 24 : 4 <297 :: AID-JGT2> 3.3.CO; 2-X , MR 1437291
- ^ 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, 10 , Amsterdam: North-Holland, págs. 801–816, MR 0382051
- ^ 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
- ^ Chudnovsky, Maria ; Seymour, Paul (2014), "Extendiendo 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
- ^ 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 : 61–99, doi : 10.1007 / BF02020444 , MR 0193025
- ^ 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
- ^ Kierstead, HA; Penrice, SG (1994), "Radio dos árboles especifican 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 limitados por chi , Open Problem Garden