Minor (gráfelmélet)

A matematika, azon belül a gráfelmélet területén a H irányítatlan gráf a G gráf minora, ha H előállítható G-ből élek és csúcsok törlésével, valamint élösszehúzás segítségével.

A gráfminorok elmélete a Wagner-tétellel kezdődött, miszerint egy gráf pontosan akkor síkbarajzolható, ha minorai között nem található meg sem a K₅ teljes gráf, sem a K_3,3 teljes páros gráf.^[1] A Robertson–Seymour-tétel szerint ezzel analóg módon, a törlések és élösszehúzások által nem befolyásolt minden gráftulajdonsághoz tartozik tiltott minorok szerinti karakterizáció.^[2] Adott H gráfra polinom idő alatt tesztelhető, hogy az a bemeneti G gráf minora-e;^[3] ebből a tiltott minorok szerinti osztályozást is tekintve az következik, hogy minden, törlések és élösszehúzások mellett is megmaradó gráftulajdonság polinom időben felismerhető.^[4]

További, a gráfminorokat érintő eredmények és sejtések közé tartozik a gráfminor-tétel, ami szerint a H-t minorként nem tartalmazó gráfok előállíthatók egyszerűbb darabok összeragasztásával, továbbá a mély Hadwiger-sejtés, ami a gráfok színezésének problémáját összeköti a nagyméretű teljes gráfminorok létezésével. A gráfminorok fajtái közül megemlítendők a topologikus minorok és az immerziós minorok.

Definíciók

Az élösszehúzás művelete során a gráfból eltávolítunk egy élt, miközben összevonjuk a két csúcsot, melyet az él kötött össze. Egy H irányítatlan gráfot akkor nevezünk a G irányítatlan gráf minorának, ha a H-val izomorf gráf előállítható G-ből élek összehúzásával, törlésével, illetve izolált csúcsok törlésével. Ezen műveletek G-n való elvégzésének sorrendje nem befolyásolja az eredményül kapott H gráfot.

A gráfminorok vizsgálata gyakran általánosabban, a matroid minorok kontextusában történik. Itt általában feltételezik, hogy a gráfok összefüggőek, megengedjük a többszörös és hurokéleket (tehát multigráfokról van szó); a hurokél összehúzása és az elválasztó élek törlése tiltott műveletnek számít. Ennek a nézőpontnak az előnye, hogy az éltörlések a gráf rangját változatlanul hagyják, az élösszehúzások pedig pontosan eggyel csökkentik.

Más kontextusokban (például a pszeudoerdők vizsgálatakor) hasznosabb lehet megengedni a nem összefüggő gráfokat és az élválasztó élek törlését, tiltani viszont a multigráfokat. Ebben a változatban az élösszehúzások után a gráfot egyszerűsíteni kell, kiküszöbölendő a hurokéleket és többszörös éleket.^[5]

Az f függvény akkor minor-monoton, ha fennáll, hogy ha H a G minora, akkor f(H) ≤ f(G).

Példa

A következő példában H a G gráf minora:

H.

G.

Ez a következő ábrán látható. Először állítsuk elő a G egy részgráfját a szaggatott élek kitörlésével, távolítsuk el a megmaradó izolált csúcsot, majd húzzuk össze a szürke élt (összevonva az általa összekötött két csúcsot):

Jelentős eredmények és sejtések

Egyszerűen ellenőrizhető, hogy a minorképzés, mint bináris reláció részbenrendezést alkot az irányítatlan gráfok izomorfizmus-osztályain: tranzitív (G minorának minora magának G-nek is minora), G és H pedig akkor és csak akkor lehetnek kölcsönösen egymás minorai, ha izomorfak egymással, mivel bármely nemtriviális minorképzési művelet éleket vagy csúcsokat szüntet meg. Neil Robertson és Paul Seymour mély eredménye szerint ez a részbenrendezés valójában egy jó előrendezés: ha tekintjük a véges gráfok G₁, G₂... végtelen listáját, mindig létezik két olyan i < j index, melyre G_i a G_j minora. Ezzel ekvivalens kijelentés, hogy gráfok tetszőleges halmazának a minorrendezést tekintve csak véges számú minimális eleme lehet.^[6] Ez az eredmény igazolta Klaus Wagner korábbi sejtését, amit Wagner-sejtésként ismertek; Wagner jóval korábban megsejtette, de csak 1970-ben publikálta.^[7]

A bizonyítás folyamata során Seymour és Robertson a gráfminor-tételt is bebizonyítják; ebben azt határozzák meg, hogy bármely rögzített H gráf esetén milyen a durva szerkezete azoknak a gráfoknak, melyek nem tartalmazzák H-t minorként. A tétel megfogalmazása igen hosszú és bonyolult, de dióhéjban azt állítja, hogy az ilyen gráfok szerkezete olyan, kisebb gráfok klikkösszegének felel meg, melyek korlátos nemszámú felületekbe beágyazott gráfokból kisebb módosításokkal előállnak. Így elméletük feltárja a gráfminorok és a gráfok topologikus beágyazásai közötti alapvető kapcsolatokat.^[8]

Bármely H esetén az egyszerű, H-minor-mentes gráfok ritkák, tehát éleik száma kisebb a csúcsok valamely konstansszorosánál.^[9] Konkrétabban, ha H csúcsainak száma h, akkor egy n-csúcsú, egyszerű, H-minormentes gráf éleinek száma legfeljebb $\scriptstyle O(nh{\sqrt {\log h}})$ lehet, és egyes K_h-minormentes gráfok rendelkeznek is ennyi éllel.^[10] Így tehát ha H csúcsainak száma h, akkor a H-minormentes gráfok átlagos fokszáma $\scriptstyle O(h{\sqrt {\log h}})$ , ezért degeneráltsága $\scriptstyle O(h{\sqrt {\log h}})$ . A H-minormentes gráfok ráadásul rendelkeznek a síkba rajzolható gráfok síkgráf-elválasztási tételéhez hasonló elválasztási tétellel: tetszőleges, rögzített H, továbbá bármely n-csúcsú H-minormentes G gráf, lehetséges olyan, $\scriptstyle O({\sqrt {n}})$ csúcsból álló részhalmazt találni, melyek eltávolítása a G-t két (esetleg nem összefüggő) részgráfba vágja szét, melyek mindegyike legfeljebb 2n/3 csúccsal rendelkezik.^[11] Ennél erősebb állítás, hogy bármely rögzített H-ra, a H-minormentes gráfok [[[favastagság]]a $\scriptstyle O({\sqrt {n}})$ .^[12]

A gráfelméleti Hadwiger-sejtés szerint ha egy G gráf nem tartalmaz a k csúcsú teljes gráffal izomorf minort, akkor G-nek létezik k − 1 színnel történő jó színezése.^[13] A k = 5 eset éppen a négyszíntétel újrafogalmazása. Hadwiger fejtését igazolták k ≤ 6-ra,^[14] de általános esetben nem tudni, igaz-e. (Bollobás, Catlin & Erdős 1980) szerint ez „a gráfelmélet egyik legmélyebb megoldatlan problémája”. A négyszíntételt gráfminorokhoz kötő másik eredmény a Robertson, Sanders, Seymour és Thomas által bejelentett snarktétel, a négyszíntétel W. T. Tutte által megsejtett megerősítése, ami azt állítja, hogy az összes olyan elválasztó élmentes 3-reguláris gráf, melynek élszínezéséhez négy színre van szükség, tartalmazza minorként a Petersen-gráfot.^[15]

A minorképzés műveletére zárt gráfcsaládok

Bővebben: Robertson–Seymour-tétel

Számos gráfcsalád rendelkezik azzal a tulajdonsággal, hogy az F-ben lévő gráf összes minora is megtalálható F-ben; az ilyen gráfcsaládot a minorképzés műveletére zártnak, röviden minorzártnak nevezzük. Például egy síkbarajzolható gráfot (vagy bármely topologikus felületbe beágyazott gráfot) tekintve sem élek eltávolításával, sem összehúzásával nem lehetséges növelni a beágyazás nemszámát; ezért mind a síkbarajzolható gráfok, mind a rögzített felületbe ágyazható gráfok minorzárt gráfcsaládokat alkotnak.

Ha F egy minorzárt család, akkor (a minorok jó előrendezési tulajdonsága miatt) az F-be nem tartozó gráfok között a minor-minimális gráfok véges X halmaza. Ezek a gráfok az F tiltott minorai: egy gráf pontosan akkor tartozik F-hez, ha nem tartalmaz minorként egyetlen, X-beli gráfot sem. Tehát minden minorzárt F család jellemezhető az X-minormentes gráfok családjaként tiltott minorok valamely véges X halmazával.^[2]

A legismertebb ilyen karakterizáció a síkbarajzolható gráfok Wagner-tétel szerinti leírása, mely szerint ezek a gráfok, melyek nem tartalmazzák sem a K₅-öt, sem a K_3,3-at minorként.^[1]

Egyes esetekben a minorzárt család tagjainak jellemzői szorosan kapcsolódnak a tiltott minorok jellemzőihez. Például az F minorzárt gráfcsalád pontosan akkor rendelkezik korlátos útszélességgel, ha a tiltott minorai között legalább egy erdő szerepel,^[16] F pontosan akkor rendelkezik korlátos famélységgel, ha tiltott minorai között szerepel útgráfok diszjunkt uniója, F pontosan akkor rendelkezik korlátos favastagsággal, ha tiltott minorjai között szerepel egy síkbarajzolható gráf,^[17] végül F pontosan akkor rendelkezik korlátos helyi favastagsággal (a gráf átmérője és favastagsága közti kapcsolat), ha tiltott minorai között szerepel egy csúcsgráf (olyan gráf, ami egyetlen csúcsa eltávolításával síkbarajzolhatóvá tehető).^[18] Amennyiben H lerajzolható a síkba úgy, hogy egyetlen élmetszés jöjjön csak létre (tehát metszési száma egy), akkor a H-minormentes gráfokhoz egy egyszerűsített gráfszerkezet-tétel tartozik, mely szerint előállíthatók síkbarajzolható gráfok és korlátos favastagságú gráfok klikkösszegeként.^[19] Például a K₅ és a K_3,3 metszési száma is egy, és ahogy Wagner megmutatta, a K₅-mentes gráfok éppen síkbarajzolható gráfok és a nyolc csúcsú Wagner-gráf 3-klikkösszegei, míg a K_3,3-mentes gráfok éppen a síkbarajzolható gráfok és a K₅ 2-klikkösszegei.^[20]

Változatok

Topologikus minorok

Egy H gráfot a G gráf topologikus minora, ha H egy felosztása izomorf G egy részgráfjával.^[21] Könnyen belátható, hogy minden topologikus minor egyben minor is. Fordítva ez nem általánosan igaz (a Petersen-gráfnak a K₅ teljes gráf ugyan minora, de nem topologikus minora), de igaz minden gráfra, melynek maximális fokszáma nem nagyobb háromnál.^[22]

A topologikus minor-reláció a véges gráfok halmazán nem jó előrendezés^[23], ezért Robertson és Seymour eredménye a topologikus minorokra nem vonatkozik. Ennek ellenére a tiltott minor-karakterizációból viszonylag egyszerűen előállítható a tiltott topologikus minor-karakterizáció.

Immerziós minorok

Egy lifting-nek, azaz felemelésnek nevezett gráfművelet központi szerepet kap az immerziók fogalomkörében. A lifting szomszédos éleken végzett művelet. Ha adott három csúcs, v, u és w, ahol (v,u) és (u,w) a gráf élei, a vuw vagy az ezzel egyenértékű (v,u), (u,w) felemelése (liftingje) az a művelet, ami törli a (v,u) és (u,w) éleket, majd hozzáadja a (v,w) élt. Amennyiben már létezett a (v,w) él, a művelet után v és w már egynél több éllel lesz összekötve, ezért a lifting alapvetően multigráf-művelet.

Amennyiben a H gráf előállítható G gráfból a G-n végzett lifting műveletek sorozatával, majd egy izomorf részgráf megtalálásával, akkor H-t a G immerziós minorjának nevezzük. Az immerziós minorok a lifting művelettel ekvivalens módon másként is definiálhatók. Azt mondjuk, H akkor egy immerziós minorja G-nek, ha létezik H csúcsaiból G csúcsaiba olyan injektív leképezés, ahol H szomszédos elemeinek képét G-ben éldiszjunkt utak kötik össze.

Az immerziós minor-reláció a véges gráfokon értelmezett jó előrendezés, ezért Robertson és Seymour eredménye az immerziós minorokra is vonatkozik. Tehát minden, immerziós minorzárt gráfcsalád rendelkezik véges tiltott immerziós minor-alapú karakterizációval.

A gráfrajzolás során az immerziós minorok a síkba nem rajzolható gráfok planarizációja során jelentkeznek: ha egy gráf metszésekkel került lerajzolásra a síkba, létrehozható egy (már síkba rajzolható) immerziós minor a metszéspontokon új csúcsok beiktatásával, közben a metszett éleket utakká felosztásával. Ez lehetővé teszi a síkbarajzolható gráfokra alkalmazott rajzolási módszerek kiterjesztését a nem síkbarajzolható gráfokra.^[24]

Korlátos mélységű minorok

Egy G gráf sekély minorja vagy korlátos mélységű minorja olyan minor, melyben G élei úgy lettek összehúzva, hogy kis átmérőjű, diszjunkt részgráfok jöjjenek létre. A korlátos mélységű minorok félúton vannak a gráfminorok és részgráfok elmélete között, amennyiben a nagyobb mélységű sekély minorok a normál gráfminorokkal esnek egybe, a 0 mélységű sekély minorok pedig éppen a részgráfok.^[25] Lehetővé teszik továbbá a gráfminorok elméletének kiterjesztését a minorképzés műveletére nézve nem zárt gráfcsaládokra, amilyenek például az 1-síkgráfok.^[26]

Párossági feltételek

A gráfminorok alternatív, az előzőekkel ekvivalens definíciója szerint H akkor G minora, amennyiben H csúcsai reprezentálhatók G csúcsdiszjunkt részfáinak olyan gyűjteményeként, melyben két, H-ban szomszédos csúcshoz mindig létezik a megfelelő G-beli két fa között húzódó él. A páratlan minorok ezt a meghatározást szigorítják a részfákra vonatkozó paritási feltételekkel. Ha H-t a fenti módon G részfáinak gyűjteménye reprezentálja, abban az esetben H akkor páratlan minorja G-nek, ha G csúcsaihoz hozzá lehet rendelni két színt úgy, hogy egy-egy részfán belül G minden éle jól színezett (végpontjai eltérő színűek), a részfák közötti szomszédosságot megjelenítő élek pedig egyszínűek (végpontjaik azonos színűek). A minoroktól eltérően a tiltott páratlan minorokkal rendelkező gráfok nem feltétlenül ritkák.^[27] A Hadwiger-sejtést, ami szerint a k-kromatikus gráfok mindig tartalmaznak k-csúcsú teljes gráfminort, szintén tanulmányozták már a páratlan minorok kontextusában.^[28]

A gráfminorok koncepciójának további, paritás-alapú kiterjesztése a páros minor, ami páros gráfot eredményez minden esetben, ha a kiindulási gráf páros. Egy H gráf akkor a páros minorja a G gráfnak, ha H előállítható G-ből csúcsok törlésével, élek törlésével, illetve a gráf egy periferikus köre mentén egymástól kettő távolságra lévő csúcspárok „összeomlasztásával” (vertex collapsing). A páros minorokra kimondható a Wagner-tétel egy formája: egy G páros gráf pontosan akkor síkbarajzolható, ha nem tartalmazza a K_3,3 teljes páros gráfot páros minorként.^[29]

Algoritmusok

Annak eldöntése, hogy G gráf tartalmazza-e H-t minorként általában NP-teljes; például ha H körgráf G-vel megegyező számú csúccsal, akkor H pontosan akkor minorja G-nek, ha G tartalmaz Hamilton-kört. Ha viszont G-t bemenetként kapjuk, H viszont rögzített, akkor polinom időben eldönthető. Konkrétabban, rögzített H esetén annak eldöntése, hogy H minorja-e G-nek, O(n³) bonyolultságú, ahol n a G csúcsainak száma, az O jelölés pedig egy konstanst rejt el, ami szuperexponenciálisan függ H-tól;^[3] az eredeti cikk óta az algoritmust O(n²) időre sikerült feljavítani.^[30] Mivel a polinom idejű algoritmussal tesztelni lehet, hogy egy gráf tartalmazza-e bármelyik tiltott minort, ezért bármely minorzárt család tagjait is polinom időben fel lehet ismerni. Ennek az eredménynek a konstruktív felhasználásához természetesen ismerni kell, hogy adott gráfcsaládnak melyek pontosan a tiltott minorjai.^[4] Néhány esetben a tiltott minorok ismertek vagy kiszámíthatóak.^[31]

Amennyiben H rögzített síkbarajzolható gráf, akkor lineáris időben tesztelhető, hogy H minorja-e a bemeneti G gráfnak.^[32] Ha H nem rögzített, akkor is ismert gyorsabb algoritmus, amennyiben G-ről tudjuk, hogy síkba rajzolható.^[33]

Fordítás

Ez a szócikk részben vagy egészben a Graph minor című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

↑ ^a ^b (Lovász 2006), p. 77; (Wagner 1937a).
↑ ^a ^b (Lovász 2006), theorem 4, p. 78; (Robertson & Seymour 2004).
↑ ^a ^b (Robertson & Seymour 1995).
↑ ^a ^b (Fellows & Langston 1988).
↑ (Lovász 2006) nem konzisztens abban, hogy megengedi-e a hurokéleket és a többszörös szomszédságokat: a 76. oldalon azt írja: „a párhuzamos élek és hurkok megengedettek”, míg a 77-ediken kijelenti: „egy gráf pontosan akkor erdő, ha nem tartalmazza a K₃ háromszöget minorként”, ami csak egyszerű gráfokra igaz.
↑ (Diestel 2005), Chapter 12: Minors, Trees, and WQO; (Robertson & Seymour 2004).
↑ (Lovász 2006), p. 76.
↑ (Lovász 2006), pp. 80–82; (Robertson & Seymour 2003).
↑ (Mader 1967).
↑ (Kostochka 1982); (Kostochka 1984); (Thomason 1984); (Thomason 2001).
↑ (Alon, Seymour & Thomas 1990); (Plotkin, Rao & Smith 1994); (Reed & Wood 2009).
↑ (Grohe 2003)
↑ (Hadwiger 1943).
↑ (Robertson, Seymour & Thomas 1993).
↑ (Thomas 1999); (Pegg 2002).
↑ (Robertson & Seymour 1983).
↑ (Lovász 2006), Theorem 9, p. 81; (Robertson & Seymour 1986).
↑ (Eppstein 2000); (Demaine & Hajiaghayi 2004).
↑ (Robertson & Seymour 1993); (Demaine, Hajiaghayi & Thilikos 2002).
↑ (Wagner 1937a); (Wagner 1937b); (Hall 1943).
↑ Diestel 2005, p. 20
↑ Diestel 2005, p. 22
↑ Ding (1996).
↑ Buchheim et al. (2014).
↑ (Nešetřil & Ossona de Mendez 2012).
↑ (Nešetřil & Ossona de Mendez 2012), pp. 319–321.
↑ Kawarabayashi, Ken-ichi; Reed, Bruce & Wollan, Paul (2011), "The graph minor algorithm with parity conditions", 52nd Annual IEEE Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers, pp. 27–36, DOI 10.1109/focs.2011.52.
↑ Geelen, Jim; Gerards, Bert & Reed, Bruce et al. (2009), "On the odd-minor variant of Hadwiger's conjecture", Journal of Combinatorial Theory, Series B 99 (1): 20–29, DOI 10.1016/j.jctb.2008.03.006.
↑ Chudnovsky, Maria; Kalai, Gil & Nevo, Eran et al. (2016), "Bipartite minors", Journal of Combinatorial Theory, Series B 116: 219–228, DOI 10.1016/j.jctb.2015.08.001.
↑ (Kawarabayashi, Kobayashi & Reed 2012).
↑ Bodlaender, Hans L. (1993. november 4.). „A Tourist Guide through Treewidth”. Acta Cybernetica 11, 1–21. o. See end of Section 5.
↑ Bodlaender, Hans L. (1993. november 4.). „A Tourist Guide through Treewidth”. Acta Cybernetica 11, 1–21. o. First paragraph after Theorem 5.3
↑ Adler, Isolde (2012. szeptember 1.). „Fast Minor Testing in Planar Graphs” (angol nyelven). Algorithmica 64 (1), 69–84. o. DOI:10.1007/s00453-011-9563-9. ISSN 0178-4617.

Alon, Noga; Seymour, Paul & Thomas, Robin (1990), "A separator theorem for nonplanar graphs", Journal of the American Mathematical Society 3 (4): 801–808, doi:10.2307/1990903, <http://www.ams.org/journals/jams/1990-03-04/S0894-0347-1990-1065053-0/home.html>.
Bollobás, B.; Catlin, P. A. & Erdős, Paul (1980), "Hadwiger's conjecture is true for almost every graph", European Journal of Combinatorics 1: 195–199, doi:10.1016/s0195-6698(80)80001-1, <http://www2.renyi.hu/~p_erdos/1980-10.pdf>. Hozzáférés ideje: 2018-02-23 Archiválva 2009. március 18-i dátummal a Wayback Machine-ben.
Buchheim, Christoph; Chimani, Markus & Gutwenger, Carsten et al. (2014), "Crossings and planarization", in Tamassia, Roberto, Handbook of Graph Drawing and Visualization, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL.
Demaine, Erik D. & Hajiaghayi, MohammadTaghi (2004), "Diameter and treewidth in minor-closed graph families, revisited", Algorithmica 40 (3): 211–215, doi:10.1007/s00453-004-1106-1, <http://erikdemaine.org/papers/DiameterTreewidth_Algorithmica/>.
Demaine, Erik D.; Hajiaghayi, MohammadTaghi & Thilikos, Dimitrios M. (2002), "1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor", Proc. 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002), vol. 2462, Lecture Notes in Computer Science, Springer-Verlag, pp. 67–80, DOI 10.1007/3-540-45753-4_8
Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4, <http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/>.
Ding, Guoli (1996), "Excluding a long double path minor", Journal of Combinatorial Theory, Series B 66 (1): 11–23, DOI 10.1006/jctb.1996.0002.
Eppstein, David (2000), "Diameter and treewidth in minor-closed graph families", Algorithmica 27: 275–291, DOI 10.1007/s004530010020.
Fellows, Michael R. & Langston, Michael A. (1988), "Nonconstructive tools for proving polynomial-time decidability", Journal of the ACM 35 (3): 727–739, DOI 10.1145/44483.44491.
Grohe, Martin (2003), "Local tree-width, excluded minors, and approximation algorithms", Combinatorica 23 (4): 613–632, doi:10.1007/s00493-003-0037-9, <http://arxiv.org/abs/math/0001128>.
Hadwiger, Hugo (1943), "Über eine Klassifikation der Streckenkomplexe", Vierteljschr. Naturforsch. Ges. Zürich 88: 133–143.
Hall, Dick Wick (1943), "A note on primitive skew curves", Bulletin of the American Mathematical Society 49 (12): 935–936, DOI 10.1090/S0002-9904-1943-08065-2.
Kawarabayashi, Ken-ichi; Kobayashi, Yusuke & Reed, Bruce (March 2012), "The disjoint paths problem in quadratic time", Journal of Combinatorial Theory, Series B 102 (2): 424–435, DOI 10.1016/j.jctb.2011.07.004
Kostochka, Alexandr V. (1982), "The minimum Hadwiger number for graphs with a given mean degree of vertices", Metody Diskret. Analiz. 38: 37–58.
Kostochka, Alexandr V. (1984), "Lower bound of the Hadwiger number of graphs by their average degree", Combinatorica 4: 307–316, DOI 10.1007/BF02579141.
Lovász, László (2006), "Graph minor theory", Bulletin of the American Mathematical Society 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.
Nešetřil, Jaroslav & Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms, vol. 28, Algorithms and Combinatorics, Springer, pp. 62–65, ISBN 978-3-642-27874-7, DOI 10.1007/978-3-642-27875-4.
Pegg, Ed, Jr. (2002), "Book Review: The Colossal Book of Mathematics", Notices of the American Mathematical Society 49 (9): 1084–1086, doi:10.1109/TED.2002.1003756, <http://www.ams.org/notices/200209/rev-pegg.pdf>.
Plotkin, Serge; Rao, Satish & Smith, Warren D. (1994), "Shallow excluded minors and improved graph decompositions", Proc. 5th ACM–SIAM Symp. on Discrete Algorithms (SODA 1994), pp. 462–470, <http://www.stanford.edu/~plotkin/lminors.ps>.
Reed, Bruce & Wood, David R. (2009), "A linear-time algorithm to find a separator in a graph excluding a minor", ACM Transactions on Algorithms 5 (4): Article 39, DOI 10.1145/1597036.1597043.
Robertson, Neil & Seymour, Paul (1983), "Graph minors. I. Excluding a forest", Journal of Combinatorial Theory, Series B 35 (1): 39–61, DOI 10.1016/0095-8956(83)90079-5.
Robertson, Neil & Seymour, Paul D. (1986), "Graph minors. V. Excluding a planar graph", Journal of Combinatorial Theory, Series B 41 (1): 92–114, DOI 10.1016/0095-8956(86)90030-4
Robertson, Neil & Seymour, Paul D. (1993), "Excluding a graph with one crossing", in Robertson, Neil & Seymour, Paul, Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors, vol. 147, Contemporary Mathematics, American Mathematical Society, pp. 669–675.
Robertson, Neil & Seymour, Paul D. (1995), "Graph Minors. XIII. The disjoint paths problem", Journal of Combinatorial Theory, Series B 63 (1): 65–110, DOI 10.1006/jctb.1995.1006.
Robertson, Neil & Seymour, Paul D. (2003), "Graph Minors. XVI. Excluding a non-planar graph", Journal of Combinatorial Theory, Series B 89 (1): 43–76, DOI 10.1016/S0095-8956(03)00042-X.
Robertson, Neil & Seymour, Paul D. (2004), "Graph Minors. XX. Wagner's conjecture", Journal of Combinatorial Theory, Series B 92 (2): 325–357, DOI 10.1016/j.jctb.2004.08.001.
Robertson, Neil; Seymour, Paul & Thomas, Robin (1993), "Hadwiger's conjecture for K₆-free graphs", Combinatorica 13: 279–361, doi:10.1007/BF01202354, <http://www.math.gatech.edu/~thomas/PAP/hadwiger.pdf>. Hozzáférés ideje: 2018-02-23.
Thomas, Robin (1999), "Recent excluded minor theorems for graphs", Surveys in combinatorics, 1999 (Canterbury), vol. 267, London Math. Soc. Lecture Note Ser., Cambridge: Cambridge Univ. Press, pp. 201–222, <http://people.math.gatech.edu/~thomas/PAP/bcc.pdf>. Hozzáférés ideje: 2018-02-23.
Thomason, Andrew (1984), "An extremal function for contractions of graphs", Mathematical Proceedings of the Cambridge Philosophical Society 95 (2): 261–265, DOI 10.1017/S0305004100061521.
Thomason, Andrew (2001), "The extremal function for complete minors", Journal of Combinatorial Theory, Series B 81 (2): 318–338, DOI 10.1006/jctb.2000.2013.
Wagner, Klaus (1937a), "Über eine Eigenschaft der ebenen Komplexe", Math. Ann. 114: 570–590, DOI 10.1007/BF01594196.
Wagner, Klaus (1937b), "Über eine Erweiterung des Satzes von Kuratowski", Deutsche Mathematik 2: 280–285.

További információk

Weisstein, Eric W.: Graph Minor (angol nyelven). Wolfram MathWorld

[w-1] (Lovász 2006), p. 77; (Wagner 1937a).

[rst-2] (Lovász 2006), theorem 4, p. 78; (Robertson & Seymour 2004).

[rs95-3] (Robertson & Seymour 1995).

[fl88-4] (Fellows & Langston 1988).

[5] (Lovász 2006) nem konzisztens abban, hogy megengedi-e a hurokéleket és a többszörös szomszédságokat: a 76. oldalon azt írja: „a párhuzamos élek és hurkok megengedettek”, míg a 77-ediken kijelenti: „egy gráf pontosan akkor erdő, ha nem tartalmazza a K₃ háromszöget minorként”, ami csak egyszerű gráfokra igaz.

[6] (Diestel 2005), Chapter 12: Minors, Trees, and WQO; (Robertson & Seymour 2004).

[7] (Lovász 2006), p. 76.

[8] (Lovász 2006), pp. 80–82; (Robertson & Seymour 2003).

[9] (Mader 1967).

[10] (Kostochka 1982); (Kostochka 1984); (Thomason 1984); (Thomason 2001).

[11] (Alon, Seymour & Thomas 1990); (Plotkin, Rao & Smith 1994); (Reed & Wood 2009).

[12] (Grohe 2003)

[13] (Hadwiger 1943).

[14] (Robertson, Seymour & Thomas 1993).

[15] (Thomas 1999); (Pegg 2002).

[16] (Robertson & Seymour 1983).

[17] (Lovász 2006), Theorem 9, p. 81; (Robertson & Seymour 1986).

[18] (Eppstein 2000); (Demaine & Hajiaghayi 2004).

[19] (Robertson & Seymour 1993); (Demaine, Hajiaghayi & Thilikos 2002).

[20] (Wagner 1937a); (Wagner 1937b); (Hall 1943).

[21] Diestel 2005, p. 20

[22] Diestel 2005, p. 22

[FOOTNOTEDing1996-23] Ding (1996).

[FOOTNOTEBuchheimChimaniGutwengerJünger2014-24] Buchheim et al. (2014).

[25] (Nešetřil & Ossona de Mendez 2012).

[26] (Nešetřil & Ossona de Mendez 2012), pp. 319–321.

[27] Kawarabayashi, Ken-ichi; Reed, Bruce & Wollan, Paul (2011), "The graph minor algorithm with parity conditions", 52nd Annual IEEE Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers, pp. 27–36, DOI 10.1109/focs.2011.52.

[28] Geelen, Jim; Gerards, Bert & Reed, Bruce et al. (2009), "On the odd-minor variant of Hadwiger's conjecture", Journal of Combinatorial Theory, Series B 99 (1): 20–29, DOI 10.1016/j.jctb.2008.03.006.

[29] Chudnovsky, Maria; Kalai, Gil & Nevo, Eran et al. (2016), "Bipartite minors", Journal of Combinatorial Theory, Series B 116: 219–228, DOI 10.1016/j.jctb.2015.08.001.

[kkr12-30] (Kawarabayashi, Kobayashi & Reed 2012).

[31] Bodlaender, Hans L. (1993. november 4.). „A Tourist Guide through Treewidth”. Acta Cybernetica 11, 1–21. o. See end of Section 5.

[32] Bodlaender, Hans L. (1993. november 4.). „A Tourist Guide through Treewidth”. Acta Cybernetica 11, 1–21. o. First paragraph after Theorem 5.3

[33] Adler, Isolde (2012. szeptember 1.). „Fast Minor Testing in Planar Graphs” (angol nyelven). Algorithmica 64 (1), 69–84. o. DOI:10.1007/s00453-011-9563-9. ISSN 0178-4617.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]