En la teoría de grafos , el número Hadwiger de un grafo no dirigido G es el tamaño de la más grande gráfico completo que se puede obtener por bordes contratantes de G . De manera equivalente, el número de Hadwiger h ( G ) es el número más grande k para el cual el gráfico completo K k es menor de G , un gráfico más pequeño obtenido de G por contracciones de aristas y eliminaciones de vértices y aristas. El número de Hadwiger también se conoce como el número de la camarilla de contracción de G [1]o el grado homomorfismo de G . [2] Se nombra después de Hugo Hadwiger , que introdujo en 1943 en conjunto con la conjetura Hadwiger , que establece que el número Hadwiger es siempre al menos tan grande como el número cromático de G .
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/0/0c/Hadwiger_conjecture.svg/260px-Hadwiger_conjecture.svg.png)
Los gráficos que tienen un número de Hadwiger como máximo cuatro han sido caracterizados por Wagner (1937) . Los gráficos con cualquier límite finito en el número de Hadwiger son escasos y tienen un número cromático pequeño. La determinación del número de Hadwiger de un gráfico es NP-difícil pero manejable con parámetros fijos .
Gráficos con pequeño número de Hadwiger
Una gráfica G tiene el número Hadwiger a lo sumo dos, si y sólo si se trata de un bosque , para un niño de tres vértice completa menor sólo se puede formar mediante la contratación de un ciclo en G .
Un gráfico tiene un número de Hadwiger como máximo tres si y solo si su ancho de árbol es como máximo dos, lo cual es cierto si y solo si cada uno de sus componentes biconectados es un gráfico en serie-paralelo .
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/4/47/Clique-sum.svg/260px-Clique-sum.svg.png)
El teorema de Wagner , que caracteriza las gráficas planas por sus menores prohibidos , implica que las gráficas planas tienen un número de Hadwiger como máximo cuatro. En el mismo trabajo que demostró este teorema, Wagner (1937) también caracterizó con mayor precisión las gráficas con número de Hadwiger como máximo cuatro: son gráficas que pueden formarse mediante operaciones de suma de clique que combinan gráficas planas con la gráfica de Wagner de ocho vértices .
Los gráficos con un número de Hadwiger como máximo cinco incluyen los gráficos de vértice y los gráficos integrables sin enlaces , los cuales tienen el gráfico completo K 6 entre sus menores prohibidos. [3]
Escasez
Cada gráfico con n vértices y número de Hadwiger k tiene bordes O ( nk √ log k ). Este límite es estrecho: para cada k , existen gráficos con el número de Hadwiger k que tienen bordes Ω ( nk √ log k ). [4] Si una gráfica G tiene un número de Hadwiger k , entonces todos sus subgrafos también tienen un número de Hadwiger como máximo k , y se deduce que G debe tener una degeneración O ( k √ log k ). Por lo tanto, las gráficas con número de Hadwiger acotado son gráficas dispersas .
Colorante
La conjetura Hadwiger establece que el número Hadwiger es siempre al menos tan grande como el número cromático de G . Es decir, cada gráfico con el número de Hadwiger k debe tener un color de gráfico con como máximo k colores. El caso k = 4 es equivalente (según la caracterización de Wagner de las gráficas con este número de Hadwiger) al teorema de los cuatro colores sobre la coloración de gráficas planas , y la conjetura también ha sido probada para k ≤ 5, pero sigue sin demostrarse para valores mayores de k . [5]
Debido a su baja degeneración, las gráficas con un número de Hadwiger como máximo k se pueden colorear mediante un algoritmo de coloración codicioso utilizando colores O ( k √ log k ).
Complejidad computacional
Probar si el número de Hadwiger de un gráfico dado es al menos un valor dado k es NP-completo , [6] de lo cual se deduce que determinar el número de Hadwiger es NP-difícil . Sin embargo, el problema es manejable con parámetros fijos : existe un algoritmo para encontrar la camarilla menor más grande en una cantidad de tiempo que depende solo polinomialmente del tamaño de la gráfica, pero exponencialmente en h ( G ). [7] Además, los algoritmos de tiempo polinomial pueden aproximar el número de Hadwiger de manera significativamente más precisa que la mejor aproximación de tiempo polinomial (asumiendo P ≠ NP) al tamaño del subgrafo completo más grande . [7]
Conceptos relacionados
El número acromático de un gráfico G es el tamaño de la mayor camarilla que se puede formar mediante la contratación de una familia de conjuntos independientes en G .
Los menores de camarilla incontables en gráficos infinitos pueden caracterizarse en términos de paraísos , que formalizan las estrategias de evasión para ciertos juegos de persecución-evasión : si el número de Hadwiger es incontable, entonces es igual al orden más grande de un refugio en el gráfico. [8]
Cada gráfico con número de Hadwiger k tiene como máximo n 2 O ( k log log k ) camarillas (subgráficos completos). [9]
Halin (1976) define una clase de parámetros de gráfico que él llama funciones S , que incluyen el número de Hadwiger. Estas funciones, desde gráficos hasta números enteros, deben ser cero en gráficos sin aristas , ser monótonas menores , [10] aumentar en uno cuando se agrega un nuevo vértice adyacente a todos los vértices anteriores, y tomar el valor más grande de los dos subgrafos a cada lado de un separador de pandillas . El conjunto de todas estas funciones forma una red completa bajo las operaciones de minimización y maximización de elementos. El elemento inferior de esta celosía es el número de Hadwiger y el elemento superior es el ancho del árbol .
Notas
- ^ Bollobás, Catlin y Erdős (1980) .
- ^ Halin (1976) .
- ^ Robertson, Seymour y Thomas (1993b) .
- ^ Kostochka (1984) ; Thomason (2001) . Las letras O y Ω en estas expresiones invocan la notación O grande .
- ^ Robertson, Seymour y Thomas (1993a) .
- ^ Eppstein (2009) .
- ↑ a b Alon, Lingas y Wahlen (2007)
- ^ Robertson, Seymour y Thomas (1991) .
- ^ Fomin, Oum y Thilikos (2010) .
- ^ Si una función f es menor-monótona, entonces si H es menor de G, entonces f (H) ≤ f (G) .
Referencias
- Alon, Noga ; Lingas, Andrzej; Wahlen, Martin (2007), "Aproximación de los problemas de homeomorfismo máximo de camarilla menor y algunos subgrafos" (PDF) , Informática teórica , 374 (1-3): 149-158, doi : 10.1016 / j.tcs.2006.12.021.
- Bollobás, B .; Catlin, PA; Erdős, Paul (1980), "La conjetura de Hadwiger es cierta para casi todos los gráficos" (PDF) , European Journal of Combinatorics , 1 : 195-199, doi : 10.1016 / s0195-6698 (80) 80001-1.
- Eppstein, David (2009), "Encontrar grandes camarillas menores es difícil", Journal of Graph Algorithms and Applications , 13 (2): 197-204, arXiv : 0807.0007 , doi : 10.7155 / jgaa.00183.
- Fomin, Fedor V .; Oum, Sang-il ; Thilikos, Dimitrios M. (2010), "Rank-width and tree-width of H -minor-free graphs", European Journal of Combinatorics , 31 (7): 1617-1628, arXiv : 0910.0079 , doi : 10.1016 / j. ejc.2010.05.003.
- Hadwiger, Hugo (1943), "Über eine Klassifikation der Streckenkomplexe", Vierteljschr. Naturforsch. Ges. Zúrich , 88 : 133–143.
- Halin, Rudolf (1976), " Funciones S para gráficos", J. Geometry , 8 (1-2): 171-186, doi : 10.1007 / BF01917434 , MR 0444522.
- Kostochka, AV (1984), "Límite inferior del número de gráficos de Hadwiger por su grado medio", Combinatorica , 4 (4): 307–316, doi : 10.1007 / BF02579141.
- Robertson, Neil ; Seymour, Paul ; Thomas, Robin (1991), "Excluyendo a los menores infinitos", Matemáticas discretas , 95 (1–3): 303–319, doi : 10.1016 / 0012-365X (91) 90343-Z , MR 1141945.
- Robertson, Neil ; Seymour, Paul ; Thomas, Robin (1993a), "Conjetura de Hadwiger para gráficos libres de K 6 " (PDF) , Combinatorica , 13 (3): 279–361, doi : 10.1007 / BF01202354.
- Robertson, Neil ; Seymour, PD ; Thomas, Robin (1993b), "Incrustaciones sin enlaces de gráficos en 3 espacios", Boletín de la American Mathematical Society , 28 (1): 84–89, arXiv : math / 9301216 , doi : 10.1090 / S0273-0979-1993- 00335-5 , MR 1164063.
- Thomason, Andrew (2001), "La función extrema para menores completos", Journal of Combinatorial Theory , Serie B, 81 (2): 318–338, doi : 10.1006 / jctb.2000.2013.
- Wagner, K. (1937), "Über eine Eigenschaft der ebenen Komplexe", Math. Ana. , 114 : 570–590, doi : 10.1007 / BF01594196.