MATH 599 - Graph Minor Theory.  Winter 2017

Instructor:

Sergey Norin
 

Telephone:

398-3819

Office:

Room 1116, Burnside Building

Office hours:

Wednesday, 1:05-3:00 PM and by appointment

Email:

snorine [at] gmail.com

Web:

http://www.math.mcgill.ca/~snorin

Lecture:

Time: Tuesday, Thursday 10:05 -11:35 AM PM.
Location: Burnside 1234

Course outline:

Graph minor theory is one of the deepest subjects in graph theory, the core of which was developed by Robertson and Seymour in a series of twenty two papers. In this course we will cover some of the central results in the theory, as well as some recent developments, including the following: 
  1. Planar graphs (Kuratowski-Wagner theorem, planarity algorithms, Lipton-Tarjan planar separator theorem, two-paths theorem)
  2. Treewidth and relatives (tree-decompositions, treewidth, excluding a planar graph, brambles, tangles, algorithms for graphs of bounded treewidth, pathwidth, separation number)
  3. The extremal function (existence, examples, Kostochka-Thomason theorem, the set of densities of minor-closed classes)
  4. Separators (Alon-Seymour-Thomas theorem, applications)
  5. Coloring graphs in minor closed classes (Hadwiger's conjecture, defective and improper colorings)
  6. Well-quasi-ordering (Kruskal's theorem, well-quasi-ordering of graphs of bounded tree-width)
  7. Graphs on surfaces (representativity, minors and disjoint paths on surfaces)
  8. The graph minor structure theorem (the tangle decomposition, surfaces, vortices, excluding a general graph, application to algorithms and well-quasi-ordering)
Notes (in progress)

Recommended reading:
  1.  R. Diestel "Graph Theory", Chapter 12.
  2.  B. Mohar and C. Thomassen "Graphs on surfaces"
  3.  L. Lovasz "Graph minor theory"
  4.  K. Kawarabayshi and B. Mohar "Some recent progress and applications in graph minor theory"

Suggested project topics:
  1. M. Devos et. al. "Excluding any graph as a minor allows a low tree-width 2-coloring"
  2. Z. Dvorak and S. N. "Treewidth of graphs with balanced separations"
  3. J. Geelen et al. "On the odd-minor variant of Hadwiger's conjecture"
  4. A. Leaf and P. Seymour "Tree-width and planar minors"
  5. C. Lee and S. Oum "Number of cliques in graphs with a forbidden subdivision"
  6. B. Oporowski, J. Oxley and R. Thomas "Typical subgraphs of 3- and 4- connected graphs"
  7. B. Reed "Mangoes and blueberries"