| Instructor: Sergey Norin |
|
907 Fine Hall | ||
|
|
|||
| Phone: | (609) 258-4234 | |||
| Office Hours: | Mondays: 2-4 PM, and by apointment |
| Grader: Josh Greene |
|
311 Fine Hall | ||
|
|
|||
| Office Hours: | Thursdays: 3-4.30 PM |
Examples of graphs, basic definitions, walks, paths, connectedness, components of a graph, cycles, cut-edges;
Trees and forests, leaves, fundamental cycles, algorithm for minimum-cost spanning tree;
Euler tours, Euler's theorem, Hamilton cycles, Dirac's theorem, bipartite graphs, odd cycles, Dijkstra's algorithm for shortest path;
Matchings in bipartite graphs, Hall's and Konig's theorems, algorithm for maximum matching in bipartite graphs;
Vertex- and edge-connectivity, Menger's theorem, digraphs, network flows, the max-flow min-cut theorem;
Stable sets, Gallai's equations, extremal problems, Ramsey theory;
Matchings in general graphs, Tutte's theorem, Petersen's theorem;
Edge-coloring, Konig's theorem, Shannon's theorem, Vizing's theorem, the Petersen graph and generalizations, vertex-coloring, Brooks' theorem, perfect graphs, the perfect graph theorem, chordal graphs;
Planar graphs, regions and cut-edges, Euler's formula, planar duals, nowhere-zero flows;
Applications of Euler's formula, the four-color theorem and its equivalents;
Minors of graphs, examples of excluded minor theorems, Kuratowski's theorem, series-parallel and outerplanar graphs;
Graphs on surfaces, Hadwiger's conjecture.