Advanced Graph Theory

Course Number: 
Hours - Lecture: 
Hours - Lab: 
Hours - Recitation: 
Hours - Total Credit: 
Typical Scheduling: 
Usually every spring semester

Selection of topics vary with each offering.



Course Text: 

No text

Topic Outline: 

Depending on the Instructor, a typical selection of the arguments covered in this course comprise the following.

  1. Matching theory (Edmonds-Gallai decomposition, ear decompositions, the matching lattice, Edmonds matching theorem, Gale-Shapley's theorem and kernel-solvable graphs, T-cuts and T-joins, Chinese postman)
  2. Connectivity (Tutte's synthesis of 3-connected graphs, Seymour's splitter theorem, excluded minor theorems, connectivity and linkages, k-connected subgraphs)
  3. Extremal problems (Szemeredi's regularity lemma and applications, Erdos-Stone theorem, the problem of Zarankiewicz, extremal problems for minors and subivisions, applications in geometry)
  4. Coloring (the Four-Color theorem, equivalent formulations and generalizations, Grotzsch' theorem and extensions, graphs on surfaces, list coloring, fractional and circular chromatic number)
  5. Ramsey theory for graphs
  6. Algebraic graph theory (Cayley graphs, the Laplacian, strongly regular graphs, isoperimetric inequalities, Colin de Verdiere's invariant)
  7. Random walks on graphs (electrical networks and random walks, hitting times, conductance and rapid mixing)
  8. The Tutte polynomial (special values of the Tutte polynomial, spanning tree expansion, polynomials of knots and links, other graph polynomials)
  9. Planar graphs (MacLane's and Whitney's criteria, planarity algorithms, uniqueness and flexibility of planar embeddings, Tutte's hamiltonicity theorem, circumference of planar graphs, separators, wye-delta reductions and applications)
  10. Geometric graph theory (crossing number, Andreev-Koebe-Thurston theorem, string graphs)
  11. Perfect graphs (polyhedral aspects, perfect matrices, Shannon capacity, Lovasz theta function, computing the chromatic and clique number of a perfect graph, graph entropy and application to sorting, imperfection ratio and the channel assignment problem)
  12. Signed graphs (totally odd K4's, nearly bipartite graphs and odd K5's, Guenin's theorem and Seymour's conjecture)
  13. Graphs on surfaces (representativity, minors and disjoint paths on surfaces,locally planar graphs, planarizing cycles)
  14. Tree-width and relatives (tree-decompositions, tree-width, excluding a planar graph, brambles, computing tree-width, algorithms, branch-width, path-width)
  15. The graph minor theorem (tree-decompositions, the tangle decomposition, surfaces, vortices, excluding a general graph, application to algorithms and well-quasi-ordering)
  16. Directed graphs (packing directed cycles and directed cuts, even cycles, disjoint branchings, orientations, directed minors, tree-width for directed graphs)