Gráfico menor

En teoría de grafos , un grafo no dirigido $H$ se denomina menor del grafo $G$ si $H$ puede formarse a partir de $G$ eliminando aristas, vértices y contrayendo aristas .

La teoría de los menores de grafos comenzó con el teorema de Wagner que sostiene que un grafo es planar si y solo si sus menores no incluyen ni al grafo completo $K 5$ ni al grafo bipartito completo $K 3,3$ . ^[1] El teorema de Robertson-Seymour implica que existe una caracterización de menor prohibido análoga para cada propiedad de los grafos que se conserva mediante eliminaciones y contracciones de aristas. ^[2] Para cada grafo fijo $H$ , es posible probar si $H$ es un menor de un grafo de entrada $G$ en tiempo polinomial ; ^[3] junto con la caracterización de menor prohibido esto implica que cada propiedad de grafo conservada mediante eliminaciones y contracciones puede reconocerse en tiempo polinomial. ^[4]

Otros resultados y conjeturas que involucran grafos menores incluyen el teorema de la estructura de grafos , según el cual los grafos que no tienen $H$ como menor pueden formarse pegando piezas más simples, y la conjetura de Hadwiger que relaciona la incapacidad de colorear un grafo con la existencia de un grafo completo grande como menor del mismo. Las variantes importantes de los grafos menores incluyen los menores topológicos y los menores de inmersión.

Definiciones

Una contracción de arista es una operación que elimina una arista de un grafo mientras fusiona simultáneamente los dos vértices que utilizó para conectar. Un grafo no dirigido $H$ es un menor de otro grafo no dirigido $G$ si se puede obtener un grafo isomorfo a $H a partir de$ $G$ contrayendo algunas aristas, eliminando algunas aristas y eliminando algunos vértices aislados. El orden en el que se realiza una secuencia de tales contracciones y eliminaciones en $G$ no afecta al grafo resultante $H$ .

Los menores de grafos se estudian a menudo en el contexto más general de los menores de matroides . En este contexto, es común suponer que todos los grafos están conectados, con bucles propios y aristas múltiples permitidas (es decir, son multigrafos en lugar de grafos simples); la contracción de un bucle y la eliminación de una arista de corte son operaciones prohibidas. Este punto de vista tiene la ventaja de que las eliminaciones de aristas dejan el rango de un grafo sin cambios, y las contracciones de aristas siempre reducen el rango en uno.

En otros contextos (como en el estudio de pseudobosques ) tiene más sentido permitir la eliminación de una arista de corte y permitir grafos desconectados, pero prohibir los multigrafos. En esta variación de la teoría de grafos menores, un grafo siempre se simplifica después de cualquier contracción de arista para eliminar sus bucles propios y aristas múltiples. ^[5]

Una función $f$ se denomina "menor-monótona" si, siempre que $H$ es menor de $G$ , se tiene $f (H ) \leq f (G)$ .

Ejemplo

En el siguiente ejemplo, el gráfico H es un menor del gráfico G :

GRAMO.

El siguiente diagrama ilustra esto. Primero se construye un subgrafo de G eliminando las aristas discontinuas (y el vértice aislado resultante) y luego se contrae la arista gris (fusionando los dos vértices que conecta):

Principales resultados y conjeturas

Es sencillo verificar que la relación de menor grafo forma un orden parcial en las clases de isomorfismo de grafos finitos no dirigidos: es transitiva (un menor de un menor de $G$ es un menor de $G$ mismo), y $G$ y $H$ solo pueden ser menores entre sí si son isomorfos porque cualquier operación menor no trivial elimina aristas o vértices. Un resultado profundo de Neil Robertson y Paul Seymour establece que este orden parcial es en realidad un cuasi-ordenamiento bien hecho : si se da una lista infinita $(G 1, G 2, \dots)$ de grafos finitos, entonces siempre existen dos índices $i < j$ tales que $G i$ es un menor de $G j$ . Otra forma equivalente de afirmar esto es que cualquier conjunto de grafos puede tener solo un número finito de elementos mínimos bajo el ordenamiento menor. ^[6] Este resultado demostró una conjetura anteriormente conocida como conjetura de Wagner, en honor a Klaus Wagner ; Wagner lo había conjeturado mucho antes, pero no lo publicó hasta 1970. ^[7]

En el curso de su demostración, Seymour y Robertson también prueban el teorema de estructura de grafos en el que determinan, para cualquier grafo fijo $H$ , la estructura aproximada de cualquier grafo que no tenga $a H$ como menor. El enunciado del teorema es en sí largo y complejo, pero en resumen establece que un grafo de este tipo debe tener la estructura de una suma de grafos más pequeños que se modifican en pequeñas formas a partir de grafos incrustados en superficies de género acotado . Por lo tanto, su teoría establece conexiones fundamentales entre los menores de grafos y las incrustaciones topológicas de grafos. ^[8]

Para cualquier grafo $H$ , los grafos simples $H -menores-libres deben ser$ dispersos , lo que significa que el número de aristas es menor que algún múltiplo constante del número de vértices. ^[9] Más específicamente, si $H$ tiene $h$ vértices, entonces un grafo simple $H -menores-libres simple$ $de n$ -vértices puede tener como máximo aristas, y algunos $K grafos$ $h$ -menores-libres tienen al menos esta cantidad de aristas. ^[10] Por lo tanto, si $H$ tiene $h$ vértices, entonces los grafos $H -menores-libres tienen$ grado medio y además degeneración . Además, los grafos $H$ -menores-libres tienen un teorema del separador similar al teorema del separador planar para grafos planares: para cualquier $H$ fijo , y cualquier grafo $H$ -menores-libres $de n$ -vértices $G$ , es posible encontrar un subconjunto de vértices cuya eliminación divide $a G$ en dos subgrafos (posiblemente desconectados) con como máximo $2$ $n$ $⁄$ $3$ vértices por subgrafo. ^[11] Aún más fuerte, para cualquier $H$ fijo , los gráficos libres de $H$ menores tienen un ancho de árbol de . ^[12] $\scriptstyle O(nh{\sqrt {\log h}})$ $\scriptstyle O(h{\sqrt {\log h}})$ $\scriptstyle O(h{\sqrt {\log h}})$ $\scriptstyle O({\sqrt {n}})$ $.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}$ $\scriptstyle O({\sqrt {n}})$

La conjetura de Hadwiger en teoría de grafos propone que si un grafo $G$ no contiene un menor isomorfo al grafo completo en $k$ vértices, entonces $G$ tiene una coloración propia con $k - 1$ colores. ^[13] El caso $k = 5$ es una reformulación del teorema de los cuatro colores . La conjetura de Hadwiger ha sido probada para $k \leq 6$ , ^[14] pero es desconocida en el caso general. Bollobás, Catlin y Erdős (1980) la llaman "uno de los problemas no resueltos más profundos en la teoría de grafos". Otro resultado que relaciona el teorema de los cuatro colores con los menores de grafos es el teorema de snark anunciado por Robertson, Sanders, Seymour y Thomas, un fortalecimiento del teorema de los cuatro colores conjeturado por WT Tutte y que establece que cualquier grafo 3-regular sin puente que requiera cuatro colores en una coloración de aristas debe tener el grafo de Petersen como menor. ^[15]

Familias de grafos cerrados menores

Muchas familias de grafos tienen la propiedad de que cada menor de un grafo en F también está en F ; se dice que una clase de este tipo es cerrada en términos de menores . Por ejemplo, en cualquier grafo plano o en cualquier incrustación de un grafo en una superficie topológica fija , ni la eliminación de aristas ni la contracción de aristas pueden aumentar el género de la incrustación; por lo tanto, los grafos planos y los grafos incrustables en cualquier superficie fija forman familias cerradas en términos de menores.

Si F es una familia cerrada en menores, entonces (debido a la propiedad de cuasiordenación de los menores) entre los grafos que no pertenecen a F hay un conjunto finito X de grafos mínimos menores. Estos grafos son menores prohibidos para F : un grafo pertenece a F si y solo si no contiene como menor a ningún grafo en X . Es decir, cada familia cerrada en menores F puede caracterizarse como la familia de grafos X -libres de menores para algún conjunto finito X de menores prohibidos. ^[2] El ejemplo más conocido de una caracterización de este tipo es el teorema de Wagner que caracteriza a los grafos planares como los grafos que no tienen ni K ₅ ni K _3,3 como menores. ^[1]

En algunos casos, las propiedades de los grafos en una familia cerrada por menores pueden estar estrechamente relacionadas con las propiedades de sus menores excluidos. Por ejemplo, una familia de grafos cerrada por menores F tiene un ancho de camino acotado si y solo si sus menores prohibidos incluyen un bosque , ^[16] F tiene una profundidad de árbol acotada si y solo si sus menores prohibidos incluyen una unión disjunta de grafos de caminos , F tiene un ancho de árbol acotado si y solo si sus menores prohibidos incluyen un grafo planar , ^[17] y F tiene un ancho de árbol local acotado (una relación funcional entre el diámetro y el ancho del árbol) si y solo si sus menores prohibidos incluyen un grafo de vértice (un grafo que puede hacerse planar mediante la eliminación de un solo vértice). ^[18] Si H puede dibujarse en el plano con un solo cruce (es decir, tiene el cruce número uno), entonces los grafos sin menores H tienen un teorema de estructura simplificado en el que se forman como sumas de camarillas de grafos planares y grafos de ancho de árbol acotado. ^[19] Por ejemplo, tanto K ₅ como K _3,3 tienen un número de cruce uno, y como Wagner mostró, los grafos libres de K ₅ son exactamente las sumas de 3 cliques de los grafos planares y el grafo de Wagner de ocho vértices , mientras que los grafos libres de K _3,3 son exactamente las sumas de 2 cliques de los grafos planares y K _5.^[20 ]

Variaciones

Menores topológicos

Un grafo H se denomina menor topológico de un grafo G si una subdivisión de H es isomorfa a un subgrafo de G. ^[21] Todo menor topológico es también un menor. Sin embargo, lo inverso no es cierto en general (por ejemplo, el grafo completo K ₅ en el grafo de Petersen es un menor pero no topológico), pero se cumple para grafos con un grado máximo no mayor que tres. ^[22]

La relación de menor topología no es un buen ordenamiento cuasi ordenado en el conjunto de grafos finitos ^[23] y por lo tanto el resultado de Robertson y Seymour no se aplica a los menores topológicos. Sin embargo, es sencillo construir caracterizaciones de menores topologías prohibidas finitas a partir de caracterizaciones de menores prohibidas finitas reemplazando cada conjunto de ramas con k aristas salientes por cada árbol en k hojas que tenga un grado descendente de al menos dos.

Menores inducidos

Un grafo H se denomina menor inducido de un grafo G si se puede obtener a partir de un subgrafo inducido de G mediante la contracción de aristas. En caso contrario, se dice que G no tiene menores inducidos por H. ^[24]

Menor de inmersión

Una operación gráfica llamada elevación es central en un concepto llamado inmersiones . La elevación es una operación sobre aristas adyacentes. Dados tres vértices v , u y w , donde (v,u) y (u,w) son aristas en el gráfico, la elevación de vuw , o equivalente de (v,u), (u,w) es la operación que elimina las dos aristas (v,u) y (u,w) y agrega la arista (v,w) . En el caso en que (v,w) ya estuviera presente, v y w ahora estarán conectados por más de una arista y, por lo tanto, esta operación es intrínsecamente una operación multigráfica.

En el caso en que un grafo H se puede obtener a partir de un grafo G mediante una secuencia de operaciones de elevación (sobre G ) y luego encontrar un subgrafo isomorfo, decimos que H es un menor de inmersión de G . Hay otra forma de definir los menores de inmersión, que es equivalente a la operación de elevación. Decimos que H es un menor de inmersión de G si existe una aplicación inyectiva de vértices en H a vértices en G donde las imágenes de elementos adyacentes de H están conectadas en G por caminos disjuntos en sus aristas.

La relación de menor inmersión es una cuasiordenación adecuada en el conjunto de grafos finitos y, por lo tanto, el resultado de Robertson y Seymour se aplica a los menores inmersión. Esto significa, además, que cada familia cerrada de menores inmersión se caracteriza por una familia finita de menores inmersión prohibidos.

En el dibujo de grafos , los menores de inmersión surgen como planarizaciones de grafos no planares : a partir de un dibujo de un grafo en el plano, con cruces, se puede formar un menor de inmersión reemplazando cada punto de cruce por un nuevo vértice, y en el proceso también subdividiendo cada borde cruzado en un camino. Esto permite que los métodos de dibujo para grafos planares se extiendan a grafos no planares. ^[25]

Menores superficiales

Un menor superficial de un grafo G es un menor en el que las aristas de G que se contrajeron para formar el menor forman una colección de subgrafos disjuntos con un diámetro bajo . Los menores superficiales interpolan entre las teorías de menores de grafos y subgrafos, en el sentido de que los menores superficiales con una profundidad alta coinciden con el tipo habitual de menor de grafos, mientras que los menores superficiales con una profundidad cero son exactamente los subgrafos. ^[26] También permiten que la teoría de los menores de grafos se extienda a clases de grafos como los grafos 1-planares que no están cerrados bajo la toma de menores. ^[27]

Condiciones de paridad

Una definición alternativa y equivalente de un grafo menor es que H es un menor de G siempre que los vértices de H puedan ser representados por una colección de subárboles de G disjuntos en sus vértices , de modo que si dos vértices son adyacentes en H , existe una arista con sus puntos finales en los dos árboles correspondientes en G. Un menor impar restringe esta definición añadiendo condiciones de paridad a estos subárboles. Si H está representado por una colección de subárboles de G como se indicó anteriormente, entonces H es un menor impar de G siempre que sea posible asignar dos colores a los vértices de G de tal manera que cada arista de G dentro de un subárbol esté coloreada correctamente (sus puntos finales tengan colores diferentes) y cada arista de G que represente una adyacencia entre dos subárboles sea monocromática (ambos puntos finales sean del mismo color). A diferencia del tipo habitual de grafos menores, los grafos con menores impares prohibidos no son necesariamente dispersos. ^[28] La conjetura de Hadwiger , de que los grafos k -cromáticos necesariamente contienen grafos completos de k -vértices como menores, también ha sido estudiada desde el punto de vista de los menores impares. ^[29]

Una extensión diferente basada en la paridad de la noción de grafos menores es el concepto de un grafo menor bipartito, que produce un grafo bipartito siempre que el grafo de partida sea bipartito. Un grafo H es un grafo menor bipartito de otro grafo G siempre que H se pueda obtener a partir de G eliminando vértices, eliminando aristas y colapsando pares de vértices que están a una distancia de dos entre sí a lo largo de un ciclo periférico del grafo. Una forma del teorema de Wagner se aplica a los grafos menores bipartitos: un grafo bipartito G es un grafo plano si y solo si no tiene el grafo de utilidad K _3,3 como un grafo menor bipartito. ^[30]

Algoritmos

El problema de decidir si un grafo G contiene a H como menor es NP-completo en general; por ejemplo, si H es un grafo de ciclo con el mismo número de vértices que G , entonces H es un menor de G si y solo si G contiene un ciclo hamiltoniano . Sin embargo, cuando G es parte de la entrada pero H es fijo, se puede resolver en tiempo polinomial. Más específicamente, el tiempo de ejecución para probar si H es un menor de G en este caso es O ( n ³ ), donde n es el número de vértices en G y la notación O grande oculta una constante que depende superexponencialmente de H ; ^[3] desde el resultado original de Graph Minors, este algoritmo se ha mejorado a tiempo O ( n ² ). ^[31] Por lo tanto, al aplicar el algoritmo de tiempo polinomial para probar si un grafo dado contiene alguno de los menores prohibidos, es teóricamente posible reconocer los miembros de cualquier familia menor-cerrada en tiempo polinomial . Este resultado no se utiliza en la práctica ya que la constante oculta es tan grande (se necesitan tres capas de notación de flecha hacia arriba de Knuth para expresarse) que descarta cualquier aplicación, lo que lo convierte en un algoritmo galáctico . ^[32] Además, para aplicar este resultado de forma constructiva, es necesario saber cuáles son los menores prohibidos de la familia de grafos. ^[4] En algunos casos, los menores prohibidos son conocidos o se pueden calcular. ^[33]

En el caso en que H es un gráfico planar fijo , entonces podemos probar en tiempo lineal en un gráfico de entrada G si H es un menor de G. ^[34] En los casos en que H no es fijo , se conocen algoritmos más rápidos en el caso en que G es planar. ^[35]

Notas

^ ab Lovász (2006), pág. 77; Wagner (1937a).
^ ab Lovász (2006), teorema 4, p. 78; Robertson y Seymour (2004).
^ por Robertson y Seymour (1995).
^ desde Fellows y Langston (1988).
^ Lovász (2006) es inconsistente sobre si se deben permitir bucles propios y adyacencias múltiples: escribe en la p. 76 que "se permiten aristas paralelas y bucles", pero en la p. 77 afirma que "un gráfico es un bosque si y solo si no contiene el triángulo $K 3$ como menor", lo cual es cierto solo para gráficos simples.
^ Diestel (2005), Capítulo 12: Menores, árboles y agua de calidad del agua; Robertson y Seymour (2004).
^ Lovász (2006), pág. 76.
^ Lovász (2006), págs. 80–82; Robertson y Seymour (2003).
^ Mader (1967).
^ Kostochka (1982); Kostochka (1984); Thomason (1984); Thomason (2001).
^ Alon, Seymour y Thomas (1990); Plotkin, Rao y Smith (1994); Reed y Wood (2009).
^ Grohe (2003)
^ Hadwiger (1943).
^ Robertson, Seymour y Thomas (1993).
^ Thomas (1999); Pegg (2002).
^ Robertson y Seymour (1983).
^ Lovász (2006), Teorema 9, p. 81; Robertson y Seymour (1986).
^ Eppstein (2000); Demaine y Hajiaghayi (2004).
^ Robertson y Seymour (1993); Demaine, Hajiaghayi y Thilikos (2002).
^ Wagner (1937a); Wagner (1937b); Hall (1943).
^ Diestel 2005, pág. 20
^ Diestel 2005, pág. 22
^ Ding (1996).
^ Blasiok y otros (2015)
^ Buchheim y otros (2014).
^ Nešetřil y Ossona de Méndez (2012).
^ Nešetřil y Ossona de Méndez (2012), págs. 319–321.
^ Kawarabayashi, Ken-ichi ; Reed, Bruce ; Wollan, Paul (2011), "El algoritmo de grafo menor con condiciones de paridad", 52.º Simposio anual IEEE sobre fundamentos de la informática , Instituto de ingenieros eléctricos y electrónicos, págs. 27-36, doi :10.1109/focs.2011.52, S2CID 17385711.
^ Geelen, Jim ; Gerards, Bert; Reed, Bruce ; Seymour, Paul ; Vetta, Adrian (2009), "Sobre la variante impar-menor de la conjetura de Hadwiger", Journal of Combinatorial Theory , Serie B, 99 (1): 20–29, doi : 10.1016/j.jctb.2008.03.006 , MR 2467815.
^ Chudnovsky, Maria ; Kalai, Gil ; Nevo, Eran; Novik, Isabella ; Seymour, Paul (2016), "Menores bipartitos", Journal of Combinatorial Theory , Serie B, 116 : 219–228, arXiv : 1312.0210 , doi :10.1016/j.jctb.2015.08.001, MR 3425242, S2CID 14571660.
^ Kawarabayashi, Kobayashi y Reed (2012).
^ Johnson, David S. (1987). "La columna de NP-completitud: una guía en curso (edición 19)". Revista de algoritmos . 8 (2): 285–303. CiteSeerX 10.1.1.114.3864 . doi :10.1016/0196-6774(87)90043-5.
^ Bodlaender, Hans L. (1993). "Una guía turística a través de Treewidth" (PDF) . Acta Cybernetica . 11 : 1–21.Véase el final de la Sección 5.
^ Bodlaender, Hans L. (1993). "Una guía turística a través de Treewidth" (PDF) . Acta Cybernetica . 11 : 1–21.Primer párrafo después del Teorema 5.3
^ Adler, Isolda; Dorn, Federico; Fomin, Fedor V.; Sau, Ignacio; Thilikos, Dimitrios M. (1 de septiembre de 2012). "Pruebas menores rápidas en gráficos planos" (PDF) . Algorítmica . 64 (1): 69–84. doi :10.1007/s00453-011-9563-9. ISSN 0178-4617. S2CID 6204674.

Referencias

Alon, Noga ; Seymour, Paul ; Thomas, Robin (1990), "Un teorema separador para gráficos no planos", Journal of the American Mathematical Society , 3 (4): 801–808, doi : 10.2307/1990903 , JSTOR 1990903, MR 1065053.
Błasiok, Jarosław; Kamiński, Marcin; Raymond, Jean-Florent; Trunck, Théophile (2015), Menores inducidos y cuasi-ordenamiento , arXiv : 1510.07135 , Bibcode :2015arXiv151007135B.
Bollobás, B. ; Catlin, PA; Erdős, Paul (1980), "La conjetura de Hadwiger es verdadera para casi todos los gráficos", European Journal of Combinatorics , 1 (3): 195–199, doi :10.1016/s0195-6698(80)80001-1.
Buchheim, Christoph; Chimani, Markus; Gutwenger, Carsten; Jünger, Michael; Mutzel, Petra (2014), "Cruces y planarización", en Tamassia, Roberto (ed.), Manual de dibujo y visualización de gráficos , Matemáticas discretas y sus aplicaciones (Boca Raton), CRC Press, Boca Raton, FL.
Demaine, Erik D. ; Hajiaghayi, MohammadTaghi (2004), "Diámetro y ancho de árbol en familias de grafos menores cerrados, revisitado", Algorithmica , 40 (3): 211–215, doi :10.1007/s00453-004-1106-1, S2CID 390856.
Demaine, Erik D. ; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios M. (2002), "1.5-Aproximación para el ancho de árbol de grafos excluyendo un grafo con un cruce como menor", Proc. 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002) , Lecture Notes in Computer Science, vol. 2462, Springer-Verlag, págs. 67–80, doi :10.1007/3-540-45753-4_8
Diestel, Reinhard (2005), Graph Theory (3.ª ed.), Berlín, Nueva York: Springer-Verlag, ISBN 978-3-540-26183-4.
Ding, Guoli (1996), "Excluyendo un menor de doble trayectoria largo", Journal of Combinatorial Theory , Serie B, 66 (1): 11–23, doi : 10.1006/jctb.1996.0002 , MR 1368512.
Eppstein, David (2000), "Diámetro y ancho de árbol en familias de grafos cerrados menores", Algorithmica , 27 (3): 275–291, arXiv : math.CO/9907126 , doi :10.1007/s004530010020, MR 1759751, S2CID 3172160.
Fellows, Michael R. ; Langston, Michael A. (1988), "Herramientas no constructivas para demostrar la decidibilidad en tiempo polinomial", Journal of the ACM , 35 (3): 727–739, doi : 10.1145/44483.44491 , S2CID 16587284.
Grohe, Martin (2003), "Ancho de árbol local, menores excluidos y algoritmos de aproximación", Combinatorica , 23 (4): 613–632, arXiv : math/0001128 , doi :10.1007/s00493-003-0037-9, S2CID 11751235.
Hadwiger, Hugo (1943), "Über eine Klassifikation der Streckkomplexe", Vierteljschr. Naturalmente. Ges. Zúrich , 88 : 133-143.
Hall, Dick Wick (1943), "Una nota sobre curvas oblicuas primitivas", Boletín de la Sociedad Matemática Americana , 49 (12): 935–936, doi : 10.1090/S0002-9904-1943-08065-2.
Kawarabayashi, Ken-ichi ; Kobayashi, Yusuke; Reed, Bruce (marzo de 2012), "El problema de los caminos disjuntos en tiempo cuadrático", Journal of Combinatorial Theory, Serie B , 102 (2): 424–435, doi : 10.1016/j.jctb.2011.07.004
Kostochka, Alexandr V. (1982), "El número mínimo de Hadwiger para grafos con un grado medio de vértices dado", Metody Diskret. Analiz. (en ruso), 38 : 37–58.
Kostochka, Alexandr V. (1984), "Límite inferior del número de Hadwiger de grafos por su grado promedio", Combinatorica , 4 (4): 307–316, doi :10.1007/BF02579141, S2CID 15736799.
Lovász, László (2006), "Teoría de gráficos menores", Boletín de la Sociedad Matemática Estadounidense , 43 (1): 75–86, doi : 10.1090/S0273-0979-05-01088-8.
Mader, Wolfgang (1967), "Homomorphieeigenschaften und mittlere Kantendichte von Graphen", Mathematische Annalen , 174 (4): 265–268, doi :10.1007/BF01364272, S2CID 120261785.
Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, vol. 28, Springer, págs. 62–65, doi :10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, Sr. 2920058.
Pegg, Ed Jr. (2002), "Reseña del libro: El colosal libro de las matemáticas" (PDF) , Avisos de la American Mathematical Society , 49 (9): 1084–1086, Bibcode :2002ITED...49.1084A, doi :10.1109/TED.2002.1003756.
Plotkin, Serge; Rao, Satish; Smith, Warren D. (1994), "Menores excluidos superficiales y descomposiciones de grafos mejoradas", Actas del 5.º Simposio ACM–SIAM sobre algoritmos discretos (SODA 1994), págs. 462–470.
Reed, Bruce ; Wood, David R. (2009), "Un algoritmo de tiempo lineal para encontrar un separador en un gráfico excluyendo un menor", ACM Transactions on Algorithms , 5 (4): Artículo 39, doi :10.1145/1597036.1597043, S2CID 760001.
Robertson, Neil ; Seymour, Paul (1983), "Grafos menores. I. Excluyendo un bosque", Journal of Combinatorial Theory, Serie B , 35 (1): 39–61, doi : 10.1016/0095-8956(83)90079-5.
Robertson, Neil ; Seymour, Paul D. (1986), "Grafos menores. V. Excluyendo un grafo planar", Journal of Combinatorial Theory, Serie B , 41 (1): 92–114, doi : 10.1016/0095-8956(86)90030-4
Robertson, Neil ; Seymour, Paul D. (1993), "Exclusión de un gráfico con un cruce", en Robertson, Neil; Seymour, Paul (eds.), Graph Structure Theory: Proc. Conferencia de investigación de verano conjunta AMS–IMS–SIAM sobre grafos menores , Contemporary Mathematics, vol. 147, American Mathematical Society , pp. 669–675.
Robertson, Neil ; Seymour, Paul D. (1995), "Graph Minors. XIII. El problema de los caminos disjuntos", Journal of Combinatorial Theory, Serie B , 63 (1): 65–110, doi : 10.1006/jctb.1995.1006.
Robertson, Neil ; Seymour, Paul D. (2003), "Graph Minors. XVI. Excluyendo un grafo no plano", Journal of Combinatorial Theory, Serie B , 89 (1): 43–76, doi :10.1016/S0095-8956(03)00042-X.
Robertson, Neil ; Seymour, Paul D. (2004), "Graph Minors. XX. La conjetura de Wagner", Journal of Combinatorial Theory, Serie B , 92 (2): 325–357, doi : 10.1016/j.jctb.2004.08.001.
Robertson, Neil ; Seymour, Paul ; Thomas, Robin (1993), "Conjetura de Hadwiger para grafos libres de K6" (PDF) , Combinatorica , 13 (3): 279–361, doi :10.1007/BF01202354, S2CID 9608738.
Thomas, Robin (1999), "Teoremas menores excluidos recientes para grafos", Encuestas sobre combinatoria, 1999 (Canterbury) (PDF) , London Math. Soc. Lecture Note Ser., vol. 267, Cambridge: Cambridge Univ. Press, págs. 201–222, MR 1725004.
Thomason, Andrew (1984), "Una función extremal para contracciones de grafos", Mathematical Proceedings of the Cambridge Philosophical Society , 95 (2): 261–265, Bibcode :1983MPCPS..95..261T, doi :10.1017/S0305004100061521, S2CID 124801301.
Thomason, Andrew (2001), "La función extremal para menores completos", Journal of Combinatorial Theory, Serie B , 81 (2): 318–338, doi : 10.1006/jctb.2000.2013.
Wagner, Klaus (1937a), "Über eine Eigenschaft der ebenen Komplexe", Math. Ana. , 114 : 570–590, doi : 10.1007/BF01594196, S2CID 123534907.
Wagner, Klaus (1937b), "Über eine Erweiterung des Satzes von Kuratowski", Deutsche Mathematik , 2 : 280–285.

Enlaces externos

Weisstein, Eric W. "Gráfico menor". MundoMatemático .