Problema sin resolver en matemáticas :
¿Todo gráfico contable tiene una partición hostil en dos partes?
En las matemáticas de grafos infinitos , una partición hostil o coloración mayoritaria es una partición de los vértices del grafo en subconjuntos disjuntos, de modo que cada vértice tiene al menos tantos vecinos en otros conjuntos como en su propio conjunto. Es una generalización del concepto de corte máximo para grafos finitos, que es automáticamente una partición hostil. (Si no, un vértice con más vecinos en su propio conjunto podría ser movido al otro conjunto, aumentando el número de aristas cortadas). La conjetura de la partición hostil es un problema sin resolver que pregunta si cada grafo contable tiene una partición hostil en dos subconjuntos. [1]
Robert H. Cowan y William R. Emerson, en un trabajo inédito, conjeturaron que todo grafo infinito tiene una partición hostil en dos subconjuntos. Sin embargo, Saharon Shelah y Eric Charles Milner refutaron la conjetura, demostrando que los grafos incontables podrían no tener particiones hostiles de dos subconjuntos. No obstante, demostraron que siempre existe una partición hostil en tres subconjuntos. [2]
Entre los grafos contables, la existencia de una partición hostil de dos subconjuntos es conocida para los siguientes casos especiales:
- Grafos que tienen un número finito de vértices de grado infinito [3]
- Grafos en los que todos los vértices tienen grado infinito, mediante un argumento que utiliza el método de ida y vuelta [1]
- Gráficos sin fin [4]
- Grafos sin subdivisión de una camarilla infinita [5]
El caso de los gráficos contables arbitrarios permanece abierto. [1]
Referencias
- ^ abc DeVos, Matthew (22 de octubre de 2007), "Particiones hostiles", Jardín de problemas abiertos
- ^ Shelah, Saharon ; Milner, EC (1990), "Gráficos sin particiones hostiles" (PDF) , en Baker, A.; Bollobás, B.; Hajnal, A. (eds.), Un tributo a Paul Erdős , Cambridge University Press, págs. 373–384, doi :10.1177/016502549001300309, MR 1117030, S2CID 143480036
- ^ Aharoni, R.; Milner, EC; Prikry, K. (1990), "Particiones hostiles de un gráfico", Journal of Combinatorial Theory , Serie B, 50 (1): 1–10, doi : 10.1016/0095-8956(90)90092-E , MR 1070461
- ^ Bruhn, Henning; Diestel, Reinhard; Georgakopoulos, Agelos; Sprüssel, Philipp (2010), "Cada gráfico sin rayos tiene una partición hostil", Combinatorica , 30 (5): 521–532, doi :10.1007/s00493-010-2590-3, MR 2776717, S2CID 9304176
- ^ Berger, Eli (2017), "Particiones hostiles para gráficos que no contienen una subdivisión de una camarilla infinita", Combinatorica , 37 (2): 157–166, doi :10.1007/s00493-015-3261-1, MR 3638340, S2CID 254028041
