Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Graph minor
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
==References== {{refbegin|2}} *{{citation | last1 = Alon | first1 = Noga | author1-link = Noga Alon | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician) | last3 = Thomas | first3 = Robin | author3-link = Robin Thomas (mathematician) | doi = 10.2307/1990903 | mr = 1065053 | journal = [[Journal of the American Mathematical Society]] | pages = 801–808 | title = A separator theorem for nonplanar graphs | issue = 4 | volume = 3 | year = 1990 | jstor = 1990903| doi-access = free }}. *{{citation | last1 = Błasiok | first1 = Jarosław | last2 = Kamiński | first2 = Marcin | last3 = Raymond | first3 = Jean-Florent | last4 = Trunck | first4 = Théophile | title = Induced minors and well-quasi-ordering | arxiv=1510.07135| bibcode = 2015arXiv151007135B| year = 2015 }}. *{{citation |last1 = Bollobás |first1 = B. |author1-link = Béla Bollobás |last2 = Catlin |first2 = P. A. |last3 = Erdős |first3 = Paul |author3-link = Paul Erdős |journal = [[European Journal of Combinatorics]] |pages = 195–199 |title = Hadwiger's conjecture is true for almost every graph |volume = 1 |issue = 3 |year = 1980 |doi = 10.1016/s0195-6698(80)80001-1 }}. *{{citation | last1 = Buchheim | first1 = Christoph | last2 = Chimani | first2 = Markus | last3 = Gutwenger | first3 = Carsten | last4 = Jünger | first4 = Michael | last5 = Mutzel | first5 = Petra | author5-link = Petra Mutzel | editor-last = Tamassia | editor-first = Roberto | editor-link = Roberto Tamassia | contribution = Crossings and planarization | publisher = CRC Press, Boca Raton, FL | series = Discrete Mathematics and its Applications (Boca Raton) | title = Handbook of Graph Drawing and Visualization | year = 2014}}. *{{citation | last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine | last2 = Hajiaghayi | first2 = MohammadTaghi | doi = 10.1007/s00453-004-1106-1 | issue = 3 | journal = Algorithmica | pages = 211–215 | title = Diameter and treewidth in minor-closed graph families, revisited | url = http://erikdemaine.org/papers/DiameterTreewidth_Algorithmica/ | volume = 40 | year = 2004| s2cid = 390856 }}. *{{citation | last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine | last2 = Hajiaghayi | first2 = MohammadTaghi | last3 = Thilikos | first3 = Dimitrios M. | contribution = 1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor | doi = 10.1007/3-540-45753-4_8 | pages = 67–80 | publisher = Springer-Verlag | series = Lecture Notes in Computer Science | title = Proc. 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002) | volume = 2462 | year = 2002}} *{{citation | last = Diestel | first = Reinhard | edition = 3rd | isbn = 978-3-540-26183-4 | location = Berlin, New York | publisher = Springer-Verlag | title = Graph Theory | url = http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ | year = 2005}}. *{{citation | last = Ding | first = Guoli | doi = 10.1006/jctb.1996.0002 | issue = 1 | journal = [[Journal of Combinatorial Theory]] | mr = 1368512 | pages = 11–23 | series = Series B | title = Excluding a long double path minor | volume = 66 | year = 1996| doi-access = free }}. *{{citation | last = Eppstein | first = David | author-link = David Eppstein | doi = 10.1007/s004530010020 | arxiv=math.CO/9907126 | mr = 1759751 | journal = Algorithmica | pages = 275–291 | title = Diameter and treewidth in minor-closed graph families | volume = 27 | issue = 3 | year = 2000| s2cid = 3172160 }}. *{{citation | last1 = Fellows | first1 = Michael R. | author1-link = Michael Fellows | last2 = Langston | first2 = Michael A. | author2-link = Michael Langston | doi = 10.1145/44483.44491 | issue = 3 | journal = [[Journal of the ACM]] | pages = 727–739 | title = Nonconstructive tools for proving polynomial-time decidability | volume = 35 | year = 1988| s2cid = 16587284 | doi-access = free }}. *{{citation | last = Grohe | first = Martin | author-link = Martin Grohe | title = Local tree-width, excluded minors, and approximation algorithms | journal = [[Combinatorica]] | doi = 10.1007/s00493-003-0037-9 | volume = 23 | issue = 4 | pages = 613–632 | year = 2003 | arxiv = math/0001128 | s2cid = 11751235 }}. *{{citation | last = Hadwiger | first = Hugo | author-link = Hugo Hadwiger | journal = Vierteljschr. Naturforsch. Ges. Zürich | pages = 133–143 | title = Über eine Klassifikation der Streckenkomplexe | volume = 88 | year = 1943}}. *{{citation | last = Hall | first = Dick Wick | doi = 10.1090/S0002-9904-1943-08065-2 | issue = 12 | journal = [[Bulletin of the American Mathematical Society]] | pages = 935–936 | title = A note on primitive skew curves | volume = 49 | year = 1943| doi-access = free }}. *{{citation | last1 = Kawarabayashi | first1 = Ken-ichi | author1-link = Ken-ichi Kawarabayashi | last2 = Kobayashi | first2 = Yusuke | last3 = Reed | first3 = Bruce | author3-link = Bruce Reed (mathematician) | title = The disjoint paths problem in quadratic time | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]] | volume = 102 | issue = 2 |date=March 2012 | pages = 424–435 | doi = 10.1016/j.jctb.2011.07.004| doi-access = free }} *{{citation | last = Kostochka | first = Alexandr V. | journal = Metody Diskret. Analiz. | language = ru | pages = 37–58 | title = The minimum Hadwiger number for graphs with a given mean degree of vertices | volume = 38 | year = 1982}}. *{{citation | last = Kostochka | first = Alexandr V. | doi = 10.1007/BF02579141 | journal = Combinatorica | pages = 307–316 | title = Lower bound of the Hadwiger number of graphs by their average degree | volume = 4 | issue = 4 | year = 1984| s2cid = 15736799 }}. *{{citation | last = Lovász | first = László | author-link = László Lovász | doi = 10.1090/S0273-0979-05-01088-8 | issue = 1 | journal = [[Bulletin of the American Mathematical Society]] | pages = 75–86 | title = Graph minor theory | volume = 43 | year = 2006| doi-access = free }}. *{{citation | last = Mader | first = Wolfgang | doi = 10.1007/BF01364272 | issue = 4 | journal = Mathematische Annalen | pages = 265–268 | title = Homomorphieeigenschaften und mittlere Kantendichte von Graphen | volume = 174 | year = 1967| s2cid = 120261785 }}. *{{citation | last1 = Nešetřil | first1 = Jaroslav | author1-link = Jaroslav Nešetřil | last2 = Ossona de Mendez | first2 = Patrice | author2-link = Patrice Ossona de Mendez | doi = 10.1007/978-3-642-27875-4 | isbn = 978-3-642-27874-7 | mr = 2920058 | pages = 62–65 | publisher = Springer | series = Algorithms and Combinatorics | title = Sparsity: Graphs, Structures, and Algorithms | volume = 28 | year = 2012 }}. *{{citation|last=Pegg|first=Ed Jr.|author-link=Ed Pegg, Jr.|title=Book Review: The Colossal Book of Mathematics|journal=Notices of the American Mathematical Society|volume=49|issue=9|year=2002|pages=1084–1086|url=https://www.ams.org/notices/200209/rev-pegg.pdf | doi = 10.1109/TED.2002.1003756|bibcode=2002ITED...49.1084A}}. *{{citation | last1 = Plotkin | first1 = Serge | last2 = Rao | first2 = Satish | last3 = Smith | first3 = Warren D. | contribution = Shallow excluded minors and improved graph decompositions | pages = 462–470 | title = Proc. 5th ACM–SIAM Symp. on Discrete Algorithms (SODA 1994) | url = http://www.stanford.edu/~plotkin/lminors.ps | year = 1994}}. *{{citation | last1 = Reed | first1 = Bruce | author1-link = Bruce Reed (mathematician) | last2 = Wood | first2 = David R. | author2-link = David Wood (mathematician) | doi = 10.1145/1597036.1597043 | issue = 4 | journal = ACM Transactions on Algorithms | pages = Article 39 | title = A linear-time algorithm to find a separator in a graph excluding a minor | volume = 5 | year = 2009| s2cid = 760001 }}. *{{citation | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician) | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician) | doi = 10.1016/0095-8956(83)90079-5 | issue = 1 | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]] | pages = 39–61 | title = Graph minors. I. Excluding a forest | volume = 35 | year = 1983| doi-access = free }}. *{{citation | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician) | last2 = Seymour | first2 = Paul D. | author2-link = Paul Seymour (mathematician) | doi = 10.1016/0095-8956(86)90030-4 | issue = 1 | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]] | pages = 92–114 | title = Graph minors. V. Excluding a planar graph | volume = 41 | year = 1986| doi-access = free }} *{{citation | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician) | last2 = Seymour | first2 = Paul D. | author2-link = Paul Seymour (mathematician) | contribution = Excluding a graph with one crossing | editor1-last = Robertson | editor1-first = Neil | editor2-last = Seymour | editor2-first = Paul | pages = 669–675 | publisher = [[American Mathematical Society]] | series = Contemporary Mathematics | title = Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors | volume = 147 | year = 1993}}. *{{citation | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician) | last2 = Seymour | first2 = Paul D. | author2-link = Paul Seymour (mathematician) | doi = 10.1006/jctb.1995.1006 | issue = 1 | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]] | pages = 65–110 | title = Graph Minors. XIII. The disjoint paths problem | volume = 63 | year = 1995| doi-access = free }}. *{{citation | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician) | last2 = Seymour | first2 = Paul D. | author2-link = Paul Seymour (mathematician) | doi = 10.1016/S0095-8956(03)00042-X | issue = 1 | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]] | pages = 43–76 | title = Graph Minors. XVI. Excluding a non-planar graph | volume = 89 | year = 2003 }}. *{{citation | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician) | last2 = Seymour | first2 = Paul D. | author2-link = Paul Seymour (mathematician) | doi = 10.1016/j.jctb.2004.08.001 | issue = 2 | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]] | pages = 325–357 | title = Graph Minors. XX. Wagner's conjecture | volume = 92 | year = 2004| doi-access = free }}. *{{citation | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician) | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician) | last3 = Thomas | first3 = Robin | author3-link = Robin Thomas (mathematician) | doi = 10.1007/BF01202354 | journal = [[Combinatorica]] | pages = 279–361 | title = Hadwiger's conjecture for ''K''<sub>6</sub>-free graphs | url = http://www.math.gatech.edu/~thomas/PAP/hadwiger.pdf | volume = 13 | year = 1993| issue = 3 | s2cid = 9608738 }}. *{{citation | last = Thomas | first = Robin | author-link = Robin Thomas (mathematician) | contribution = Recent excluded minor theorems for graphs | location = Cambridge | mr = 1725004 | pages = 201–222 | publisher = Cambridge Univ. Press | series = London Math. Soc. Lecture Note Ser. | title = Surveys in combinatorics, 1999 (Canterbury) | url=http://people.math.gatech.edu/~thomas/PAP/bcc.pdf | volume = 267 | year = 1999}}. *{{citation | last = Thomason | first = Andrew | doi = 10.1017/S0305004100061521 | issue = 2 | journal = [[Mathematical Proceedings of the Cambridge Philosophical Society]] | pages = 261–265 | title = An extremal function for contractions of graphs | volume = 95 | year = 1984| bibcode = 1983MPCPS..95..261T | s2cid = 124801301 }}. *{{citation | last = Thomason | first = Andrew | doi = 10.1006/jctb.2000.2013 | issue = 2 | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]] | pages = 318–338 | title = The extremal function for complete minors | volume = 81 | year = 2001| doi-access = free }}. *{{citation | last = Wagner | first = Klaus | author-link = Klaus Wagner | doi = 10.1007/BF01594196 | journal = Math. Ann. | pages = 570–590 | title = Über eine Eigenschaft der ebenen Komplexe | volume = 114 | year = 1937a| s2cid = 123534907 }}. *{{citation | last = Wagner | first = Klaus | author-link = Klaus Wagner | journal = Deutsche Mathematik | pages = 280–285 | title = Über eine Erweiterung des Satzes von Kuratowski | volume = 2 | year = 1937b}}. {{refend}}
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)