Минор графа

Минор в теории графов — граф $\text{[math]}$ $\text{[math]}$ $H$ $H$ для заданного графа $\text{[math]}$ $\text{[math]}$ $G$ $G$ , который может быть образован из $\text{[math]}$ $\text{[math]}$ $G$ $G$ удалением рёбер и вершин и стягиванием рёбер.

Теория миноров графов началась с теоремы Вагнера, гласящей, что граф планарен в том и только в том случае, когда в его миноры не входят ни полный граф K₅, ни полный двудольный граф K_3,3^[1]^[2]. Из теоремы Робертсона — Сеймура следует, что аналоги характеризации запрещёнными минорами существуют для любого свойства графов, которые сохраняются при удалениях и стягивании рёбер^[3]^[4].

Для любого графа H можно проверить, является ли H минором входного графа G за полиномиальное время^[5]. Вместе с характеризацией запрещёнными минорами из этого следует, что любое свойство графа, сохраняющееся при удалениях и стягиваниях, может быть распознано за полиномиальное время^[6].

Среди других результатов и гипотез, использующих миноры графов, находятся теорема о структуре графа, согласно которой графы, не содержащие H в качестве минора, могут быть образованы склеиванием более простых частей, и гипотеза Хадвигера, связывающая невозможность раскраски графа с существованием большого полного графа в качестве его минора. Важными вариантами миноров графов являются топологические миноры и погружённые миноры.

ОпределенияПравить

Стягивание ребра — это операция, которая удаляет ребро из графа, а концы ребра сливаются в одну вершину. Неориентированный граф H является минором другого неориентированного графа G, если граф, изоморфный H, может быть получен из G стягиванием рёбер, удалением некоторых рёбер и удалением некоторых изолированных вершин. Порядок, в котором производится стягивания и удаления в G, не влияют на результирующий граф H.

Миноры графов часто изучаются в более общем контексте миноров матроидов^[en]. В этом контексте обычно полагается, что графы связны, могут иметь петли и multiple edge (то есть, рассматриваются мультиграфы, а не простые графы). Стягивание петли и удаление разрезающего ребра запрещены. При таком подходе удаление ребра оставляет ранг графа неизменным, а стягивание ребра всегда уменьшает ранг на единицу.

В других контекстах (как, например, при изучении псевдолесов) имеет смысл разрешить удаление разрезающих рёбер и позволить графам быть несвязными, но при этом имеет смысл запретить мультиграфы. В таком варианте теории миноров графов граф всегда упрощается после любого стягивания ребра для исключения петель и кратных рёбер^[7]

ПримерПравить

В следующем примере граф H является минором графа G:

H.

G.

Следующий рисунок иллюстрирует это. Сначала строим подграф графа G путём удаления пунктирных рёбер (и возникающую изолированную вершину), а затем стягиваем серое ребро (объединяя две вершины, которые ребро соединяет):

Основные результаты и гипотезыПравить

Можно легко проверить, что отношение миноров графов образует частичный порядок на классе изоморфизмов неориентированных графов — отношение транзитивно (минор минора графа G является сам минором G) и графы G и H могут быть минорами друг друга если они изоморфны, поскольку любая нетривиальная операция с минором удаляет рёбра или вершины. Глубокий результат Нейла Робертсона^[en] и Пола Сеймура утверждает, что этот частичный порядок является, на самом деле, вполне квазиупорядоченным^[en] — если задан бесконечный список G₁, G₂,… конечных графов, всегда существуют два индекса i < j, такие что G_i является минором графа G_j. Эквивалентная формулировка утверждения — любое множество графов может иметь лишь конечное число минимальных элементов по минорному отношению^[8]. Этот результат доказывает гипотезу, до этого известную как гипотеза Вагнера. Вагнер высказал гипотезу много раньше, но опубликовал её лишь в 1970^[9].

По ходу доказательства Сеймур и Робертсон также доказали теорему о структуре графа, в которой они определили для любого фиксированного графа H грубую структуру любого графа, который не содержит H в качестве минора. Утверждение теоремы длинно и запутано, но, вкратце, теорема устанавливает, что такой граф должен иметь структуру суммы по кликам меньших графов, которые получаются небольшой модификацией графов, вложенных в поверхности ограниченного рода. Таким образом, их теория устанавливает фундаментальную связь между минорами графа и топологическими вложениями графов^[10]^[11].

Для любого графа H простые свободные от миноров H графы должны быть редкими, что означает, что число рёбер меньше некоторой константы, умноженной на число вершин^[12]. Конкретнее, если H имеет h вершин, то простой n-вершинный свободный от H-миноров граф может иметь не более $\text{[math]}$ $\text{[math]}$ $\scriptstyle O(nh{\sqrt {\log h}})$ рёбер, а некоторые свободные от K_h миноров графы имеют по меньшей мере такое число рёбер^[13]. Так, если H имеет h вершин, то свободные от H-миноров графы имеют среднюю степень $\text{[math]}$ $\text{[math]}$ $\scriptstyle O(h{\sqrt {\log h}})$ и, кроме того, вырожденность $\text{[math]}$ $\text{[math]}$ $\scriptstyle O(h{\sqrt {\log h}})$ . Вдобавок, свободные от H-миноров графы имеют теорему о разбиении, подобную теореме о разбиении в планарном графе — для любого фиксированного H, и любого n-вершинного свободного от H-миноров графа G можно найти подмножество вершин размером $\text{[math]}$ $\text{[math]}$ $\scriptstyle O({\sqrt {n}})$ , удаление которого делит граф G на два (возможно несвязных) подграфа с максимум 2n/3 вершинами в каждом^[14]. Даже более строго, для любого фиксированного H свободные от H-миноров графы имеют древесную ширину $\text{[math]}$ $\text{[math]}$ $\scriptstyle O({\sqrt {n}})$ ^[15].

Гипотеза Хадвигера делает предположение, что если граф G не содержит минор, изоморфный полному графу с k вершинами, то граф G имеет правильную раскраску в k − 1 цветов^[16]. Случай k = 5 является переформулировкой проблемы четырёх красок. Гипотеза Хадвигера доказана для k ≤ 6 ^[17], но не в общем виде. Болобас, Катлин и Эрдёш^[18] назвали задачу «одной из глубочайших нерешённых задач теории графов». Другой результат, связывающий теорему четырёх красок с минорами графа — это теорема о снарках, о доказательстве которой объявили Робертсон, Сандерс, Сеймур и Томас^[19]. Теорема является усилением теоремы четырёх красок и была высказана (как гипотеза) Таттом и она утверждает, что любой 3-регулярный граф без мостов, для рёберной раскраски которого требуется четыре цвета, должен содержать граф Петерсена в качестве минора^[20]^[21].

Семейства графов, замкнутые по минорамПравить

Многие семейства графов обладают свойством, что любой минор графа из F также входит в F. В этом случае говорят, что класс графов минорно замкнут. Например, для любого планарного графа или вложения графа в фиксированную топологическую поверхность ни удаление рёбер, ни стягивание рёбер не может увеличить род вложения. Таким образом, планарные графы и графы, вложимые в любую фиксированную поверхность, образуют минорно замкнутые семейства.

Если F является минорно замкнутым семейством, то (ввиду свойства вполне квазиупорядоченности миноров) среди графов, не принадлежащих F, существует конечное множество X минорно минимальных графов. Эти графы являются запрещёнными минорами для F — граф принадлежит множеству F тогда и только тогда, когда он не содержит в качестве миноров любой граф из X. Таким образом, любое минорно замкнутое семейство F может быть охарактеризовано как семейство свободных от миноров из X графов для некоторого конечного множества X запрещённых миноров^[3]^[4].

Хорошо известным примером характеризации такого типа является Теорема Вагнера, характеризующая планарные графы как графы, не имеющие ни K₅, ни K_3,3 в качестве миноров ^[1]^[2].

В некоторых случаях свойства графов в минорно замкнутом семействе может быть тесно связана со свойствами исключённых миноров. Например, минорно замкнутое семейство графов F имеет ограниченную путевую тогда и только тогда, когда запрещённые семейство семейства включает лес ^[22], F имеет ограниченную глубину дерева тогда и только тогда, когда запрещённые миноры включают разъединённое объединение путей, F имеет ограниченную древесную ширину тогда и только тогда, когда его запрещённые миноры включают планарный граф^[23], и F имеет ограниченную локальную древесную ширину (функциональную связь между диаметром и древесной шириной) тогда и только тогда, когда его запрещённые миноры включают верхушечный граф (граф, который становится планарным при удалении одной вершины)^[24]^[25]. Если H может быть нарисован на плоскости с единственным пересечением (то есть, число пересечений графа равно единице), то для свободных от H-миноров графов верна теорема об упрощённой структуре, по которой такие графы представляют собой кликовую сумму планарных графов и графов с ограниченной древесной шириной^[26]^[27]. Например, как K₅, так и K_3,3 имеют число пересечений, равное единице, и как показал Вагнер, свободные от K₅ графы — это в точности 3-кликовые суммы планарных графов и восьмивершинного графа Вагнера, в то время как свободные от K_3,3 графы — это в точности 2-кликовые суммы планарных графов и K₅^[28].

ВариацииПравить

Топологические минорыПравить

Граф H называется топологическим минором графа G, если граф подразбиений графа H изоморфен подграфу графа G ^[29]. Легко видеть, что любой топологический минор является минором (в обычном смысле). Обратное, однако, в общем случае неверно (например, полный граф K₅ в графе Петерсена является минором, но не является топологическим минором), но выполняется для графа с максимальной степенью, не превосходящей трёх^[30].

Отношения топологических миноров не является вполне квазиупорядоченным на множестве конечных графов^[31] и потому результат Робертсона и Сеймура неприменим к топологическим минорам. Однако легко построить характеризации конечными запрещёнными топологическими минорами из характеризации конечными запрещёнными минорами.

Погружённый минорПравить

Операция с графом, называемая подъёмом, является центральным понятием в концепции погружения. Подъём является операцией со смежными рёбрами. Если заданы три вершины v, u и w, где (v, u) и (u, w) — ребра графа, подъём vuw, или, эквивалентно, (v, u), (u, w) — это операция, которая удаляет два ребра (v, u) и (u, w) и добавляет ребро (v, w). В случае, когда ребро (v, w) уже присутствует, v и w будут соединены ещё одним ребром, а поэтому операция является существенно операцией с мультиграфами.

В случае, когда граф H может быть получен из графа G путём последовательности операций подъёма (над G) а затем нахождения изоморфного подграфа, мы говорим, что H является погружённым минором графа G.

Существует другой способ определения погружённых миноров, который эквивалентен операции подъёма. Мы говорим, что H является погружённым минором графа G, если существует инъективное отображение из вершин H в вершины G, при котором образы смежных элементов H соединены в G путями, не имеющими общих рёбер.

Отношение погружённых миноров является вполне квазиупорядоченным на множестве конечных графов, а потому результаты Роебртсона и Сеймура применимы к погружённым минорам. Более того, это означает, что любое семейство, замкнутое по погружённым минорам, характеризуется конечным семейством запрещённых вложенных миноров.

В области визуализация графов погружённые миноры появляются как планаризации^[en] непланарных графов — из рисунка графа на плоскости с пересечениями может быть образован погружённый минор путём замены каждой точки пересечения новой вершиной и разбиения каждого пересечённого ребра на путь. Это позволяет распространить методы рисования планарных графов на непланарные графы ^[32].

Неглубокие минорыПравить

Неглубокий минор графа G — это минор, в котором рёбра графа G, стянутые для получения минора, образуют непересекающиеся подграфы малого диаметра. Неглубокие миноры образуют как бы мост между минорами графа и подграфами в том смысле, что неглубокие миноры с высокой глубиной совпадают с обычными типами миноров, в то время как неглубокие миноры с нулевой глубиной — это в точности подграфы^[33]. Они также позволяют распространить теорию миноров графа на классы графов, такие как 1-планарные графы, которые не замкнуты по взятию миноров^[34].

АлгоритмыПравить

Задача разрешимости, содержится ли граф H в графе G в качестве минора является, в общем случае, NP-полной. Например, если H является циклом с тем же числом вершин, что и у G, то H является минором графа G тогда и только тогда, когда G содержит гамильтонов граф. Однако, если G является входным, а H фиксирован, задача может быть решена за полиномиальное время. Конкретнее, время работы проверки, является ли H минором графа G в этом случае равно O(n³), где n — число вершин в G, а O большое прячет константу, которая зависит суперэкспоненциально от H^[5]. Вследствие результата о минорах графа этот алгоритм улучшается до O(n²)^[35]. Таким образом, при применении алгоритма с полиномиальным временем работы для проверки, содержит ли заданный граф какой-либо из запрещённых миноров, можно распознать члены любого минорно замкнутого семейства за полиномиальное время. Однако, чтобы применять этот результат конструктивно, необходимо знать запрещённые миноры семейства графов^[6].

ПримечанияПравить

↑ ¹ ² Lovász, 2006, p. 77.
↑ ¹ ² Wagner, 1937a.
↑ ¹ ² Lovász, 2006, Т. 4, p. 78.
↑ ¹ ² Robertson, Seymour, 2004.
↑ ¹ ² Robertson, Seymour, 1995.
↑ ¹ ² Fellows, Langston, 1988.
↑ Ловаш (Lovász (2006)) противоречит сам себе. На странице 76 он пишет, что «параллельные рёбра и петли разрешаются», но на странице 77 от утверждает, что «граф является лесом тогда и только тогда, когда он не содержит треугольника K₃ в качестве минора», что верно только для простых графов.
↑ Diestel (2005), Chapter 12: Minors, Trees, and WQO; Robertson, Seymour (2004).
↑ Lovász, 2006, p. 76.
↑ Lovász, 2006, p. 80—82.
↑ Robertson, Seymour, 2003.
↑ Mader, 1967.
↑ 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.
↑ Bollobás, Catlin, Erdős, 1980.
↑ Однако по состоянию на 2012 год доказательство опубликовано так и не было
↑ 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; Hall, 1943.
↑ Diestel, 2005, p. 20.
↑ Diestel, 2005, p. 22.
↑ Ding, 1996.
↑ Buchheim, Chimani, Gutwenger, Jünger, Mutzel, 2014.
↑ Nešetřil, de Mendez, 2012.
↑ Nešetřil, de Mendez, 2012, p. 319—321.
↑ Kawarabayashi, Kobayashi, Reed, 2012.

ЛитератураПравить

Noga Alon, Paul Seymour, Robin Thomas. A separator theorem for nonplanar graphs // Journal of the American Mathematical Society. — 1990. — Т. 3, вып. 4. — С. 801—808. — doi:10.2307/1990903. — JSTOR 1990903.
B. Bollobás, P. A. Catlin, Paul Erdős. Hadwiger's conjecture is true for almost every graph // European Journal of Combinatorics. — 1980. — Т. 1. — С. 195—199. — doi:10.1016/s0195-6698(80)80001-1. Архивировано 18 марта 2009 года.
Christoph Buchheim, Markus Chimani, Carsten Gutwenger, Michael Jünger, Petra Mutzel. Handbook of Graph Drawing and Visualization / Roberto Tamassia. — CRC Press, Boca Raton, FL, 2014. — (Discrete Mathematics and its Applications (Boca Raton)).
Erik D. Demaine, MohammadTaghi Hajiaghayi. Diameter and treewidth in minor-closed graph families, revisited // Algorithmica. — 2004. — Т. 40, вып. 3. — С. 211—215. — doi:10.1007/s00453-004-1106-1.
Erik D. Demaine, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos. Proc. 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002). — Springer-Verlag, 2002. — Т. 2462. — С. 67—80. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-45753-4_8.
Reinhard Diestel. Graph Theory. — 3rd. — Berlin, New York: Springer-Verlag, 2005. — ISBN 978-3-540-26183-4.
Guoli Ding. Excluding a long double path minor // Journal of Combinatorial Theory. — 1996. — Т. 66, вып. 1. — С. 11—23. — doi:10.1006/jctb.1996.0002.
David Eppstein. Diameter and treewidth in minor-closed graph families // Algorithmica. — 2000. — Т. 27. — С. 275—291. — doi:10.1007/s004530010020. — arXiv:math.CO/9907126.
Michael R. Fellows, Michael A. Langston. Nonconstructive tools for proving polynomial-time decidability // Journal of the ACM. — 1988. — Т. 35, вып. 3. — С. 727—739. — doi:10.1145/44483.44491.
Martin Grohe. Local tree-width, excluded minors, and approximation algorithms // Combinatorica. — 2003. — Т. 23, вып. 4. — С. 613—632. — doi:10.1007/s00493-003-0037-9.
Hugo Hadwiger. Über eine Klassifikation der Streckenkomplexe // Vierteljschr. Naturforsch. Ges. Zürich. — 1943. — Т. 88. — С. 133—143.
Dick Wick Hall. A note on primitive skew curves // Bulletin of the American Mathematical Society. — 1943. — Т. 49, вып. 12. — С. 935—936. — doi:10.1090/S0002-9904-1943-08065-2.
Ken-ichi Kawarabayashi, Yusuke Kobayashi, Bruce Reed. The disjoint paths problem in quadratic time // Journal of Combinatorial Theory, Series B. — 2012. — Т. 102, вып. 2. — С. 424—435. — doi:10.1016/j.jctb.2011.07.004.
Косточка А. В. О минимуме числа Хадвигера для графов с данной средней степенью вершин. — Новосибирск: Институт математики СО АН СССР, 1982. — Вып. 38. — С. 37—58.
Alexandr V. Kostochka. Lower bound of the Hadwiger number of graphs by their average degree // Combinatorica. — 1984. — Т. 4. — С. 307—316. — doi:10.1007/BF02579141.
László Lovász. Graph minor theory // Bulletin of the American Mathematical Society. — 2006. — Т. 43, вып. 1. — С. 75—86. — doi:10.1090/S0273-0979-05-01088-8.
Wolfgang Mader. Homomorphieeigenschaften und mittlere Kantendichte von Graphen // Mathematische Annalen. — 1967. — Т. 174, вып. 4. — С. 265—268. — doi:10.1007/BF01364272.
Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms. — Springer, 2012. — Т. 28. — С. 62–65. — (Algorithms and Combinatorics). — ISBN 978-3-642-27874-7. — doi:10.1007/978-3-642-27875-4.
Ed Pegg Jr. Book Review: The Colossal Book of Mathematics // Notices of the American Mathematical Society. — 2002. — Т. 49, вып. 9. — С. 1084—1086. — doi:10.1109/TED.2002.1003756.
Serge Plotkin, Satish Rao, Warren D. Smith. Proc. 5th ACM–SIAM Symp. on Discrete Algorithms (SODA 1994). — 1994. — С. 462—470.
Bruce Reed, David R. Wood. A linear-time algorithm to find a separator in a graph excluding a minor // ACM Transactions on Algorithms. — 2009. — Т. 5, вып. 4. — С. Article 39. — doi:10.1145/1597036.1597043.
Neil Robertson, Paul Seymour. Graph minors. I. Excluding a forest // Journal of Combinatorial Theory, Series B. — 1983. — Т. 35, вып. 1. — С. 39—61. — doi:10.1016/0095-8956(83)90079-5.
Neil Robertson, Paul D. Seymour. Graph minors. V. Excluding a planar graph // Journal of Combinatorial Theory, Series B. — 1986. — Т. 41, вып. 1. — С. 92—114. — doi:10.1016/0095-8956(86)90030-4.
Neil Robertson, Paul D. Seymour. Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors / Neil Robertson, Paul Seymour. — American Mathematical Society, 1993. — Т. 147. — С. 669–675. — (Contemporary Mathematics).
Neil Robertson, Paul D. Seymour. Graph Minors. XIII. The disjoint paths problem // Journal of Combinatorial Theory, Series B. — 1995. — Т. 63, вып. 1. — С. 65—110. — doi:10.1006/jctb.1995.1006.
Neil Robertson, Paul D. Seymour. Graph Minors. XVI. Excluding a non-planar graph // Journal of Combinatorial Theory, Series B. — 2003. — Т. 89, вып. 1. — С. 43—76. — doi:10.1016/S0095-8956(03)00042-X.
Neil Robertson, Paul D. Seymour. Graph Minors. XX. Wagner's conjecture // Journal of Combinatorial Theory, Series B. — 2004. — Т. 92, вып. 2. — С. 325—357. — doi:10.1016/j.jctb.2004.08.001.
Neil Robertson, Paul Seymour, Robin Thomas. Hadwiger's conjecture for K₆-free graphs // Combinatorica. — 1993. — Т. 13. — С. 279—361. — doi:10.1007/BF01202354.
Robin Thomas. Surveys in combinatorics, 1999 (Canterbury). — Cambridge: Cambridge Univ. Press, 1999. — Т. 267. — С. 201—222. — (London Math. Soc. Lecture Note Ser.).
Andrew Thomason. An extremal function for contractions of graphs // Mathematical Proceedings of the Cambridge Philosophical Society. — 1984. — Т. 95, вып. 2. — С. 261—265. — doi:10.1017/S0305004100061521.
Andrew Thomason. The extremal function for complete minors // Journal of Combinatorial Theory, Series B. — 2001. — Т. 81, вып. 2. — С. 318—338. — doi:10.1006/jctb.2000.2013.
Klaus Wagner. Über eine Eigenschaft der ebenen Komplexe // Math. Ann.. — 1937a. — Т. 114. — С. 570—590. — doi:10.1007/BF01594196.
Andrew Thomason. Über eine Erweiterung des Satzes von Kuratowski // Deutsche Mathematik. — 1937b. — Т. 2. — С. 280—285.

СсылкиПравить

Weisstein, Eric W. Graph Minor (англ.) на сайте Wolfram MathWorld.

[_bd8721414eb62711-1] ¹ ² Lovász, 2006, p. 77.

[_4dd471f52bd9bd4c-2] ¹ ² Wagner, 1937a.

[_e865905b1c0784e0-3] ¹ ² Lovász, 2006, Т. 4, p. 78.

[_8189aeb928bba497-4] ¹ ² Robertson, Seymour, 2004.

[_a7d5580029f437b1-5] ¹ ² Robertson, Seymour, 1995.

[_a7714ec87b8497a3-6] ¹ ² Fellows, Langston, 1988.

[7] Ловаш (Lovász (2006)) противоречит сам себе. На странице 76 он пишет, что «параллельные рёбра и петли разрешаются», но на странице 77 от утверждает, что «граф является лесом тогда и только тогда, когда он не содержит треугольника K₃ в качестве минора», что верно только для простых графов.

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

[_bd8721414eb62710-9] Lovász, 2006, p. 76.

[_10d53848e5c31bd9-10] Lovász, 2006, p. 80—82.

[_7a5e06b4da97bd9c-11] Robertson, Seymour, 2003.

[_a519256cbcab71cd-12] Mader, 1967.

[13] Kostochka, 1984; Thomason, 1984; Thomason, 2001.

[14] Alon, Seymour, Thomas, 1990; Plotkin, Rao, Smith, 1994; Reed, Wood, 2009.

[_086a3707c016bccf-15] Grohe, 2003.

[_b7e35c5c20865769-16] Hadwiger, 1943.

[_1702ca4c74d13d63-17] Robertson, Seymour, Thomas, 1993.

[_9c6114ba445fcb6d-18] Bollobás, Catlin, Erdős, 1980.

[19] Однако по состоянию на 2012 год доказательство опубликовано так и не было

[_3414213a4d95875d-20] Thomas, 1999.

[_708d4a84e6d0aab0-21] Pegg, 2002.

[_02a6a1614224f020-22] Robertson, Seymour, 1983.

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

[_852e4d3e36d7d1b7-24] Eppstein, 2000.

[_4e7ea7f5b9a7465b-25] Demaine, Hajiaghayi, 2004.

[_96d2333c393d6687-26] Robertson, Seymour, 1993.

[_15c96bf3bc3a929a-27] Demaine, Hajiaghayi, Thilikos, 2002.

[28] Wagner, 1937a; Hall, 1943.

[_8e1528ddc612cc4a-29] Diestel, 2005, p. 20.

[_8e1528ddc612cc48-30] Diestel, 2005, p. 22.

[_0bdab8deeb3282ce-31] Ding, 1996.

[_683439a2f7f8bfa2-32] Buchheim, Chimani, Gutwenger, Jünger, Mutzel, 2014.

[_07e3be09af5ade09-33] Nešetřil, de Mendez, 2012.

[_a6269cff34724a40-34] Nešetřil, de Mendez, 2012, p. 319—321.

[_c0a2462374d97a73-35] Kawarabayashi, Kobayashi, Reed, 2012.

[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]

[34]

[35]