- You are here:
- Home

Department:

MATH

Course Number:

7014

Hours - Lecture:

3

Hours - Lab:

0

Hours - Recitation:

0

Hours - Total Credit:

3

Typical Scheduling:

Usually every spring semester

Selection of topics vary with each offering.

Prerequisites:

None

Course Text:

No text

Topic Outline:

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

- 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)
- Connectivity (Tutte's synthesis of 3-connected graphs, Seymour's splitter theorem, excluded minor theorems, connectivity and linkages, k-connected subgraphs)
- Extremal problems (Szemeredi's regularity lemma and applications, Erdos-Stone theorem, the problem of Zarankiewicz, extremal problems for minors and subivisions, applications in geometry)
- Coloring (the Four-Color theorem, equivalent formulations and generalizations, Grotzsch' theorem and extensions, graphs on surfaces, list coloring, fractional and circular chromatic number)
- Ramsey theory for graphs
- Algebraic graph theory (Cayley graphs, the Laplacian, strongly regular graphs, isoperimetric inequalities, Colin de Verdiere's invariant)
- Random walks on graphs (electrical networks and random walks, hitting times, conductance and rapid mixing)
- The Tutte polynomial (special values of the Tutte polynomial, spanning tree expansion, polynomials of knots and links, other graph polynomials)
- 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)
- Geometric graph theory (crossing number, Andreev-Koebe-Thurston theorem, string graphs)
- 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)
- Signed graphs (totally odd K4's, nearly bipartite graphs and odd K5's, Guenin's theorem and Seymour's conjecture)
- Graphs on surfaces (representativity, minors and disjoint paths on surfaces,locally planar graphs, planarizing cycles)
- Tree-width and relatives (tree-decompositions, tree-width, excluding a planar graph, brambles, computing tree-width, algorithms, branch-width, path-width)
- The graph minor theorem (tree-decompositions, the tangle decomposition, surfaces, vortices, excluding a general graph, application to algorithms and well-quasi-ordering)
- Directed graphs (packing directed cycles and directed cuts, even cycles, disjoint branchings, orientations, directed minors, tree-width for directed graphs)