MA 6103 Graph Theory

3 Credits

This course covers: Graphs and digraphs, subgraphs, paths, cycles, trees and forests. Contraction and minors. Vertex-connectivity and edge-connectivity. Structure of k-connected graphs. Menger’s theorem. Planar graphs, drawings and embeddings. Graph colorings: vertex-coloring, edge-coloring, listcoloring. Perfect graphs. Network flows, Ford- Fulkerson Theorem. Matching, Packing and Covering. Ramsey theory. Extremal graph theory, Szemeredi’s regularity lemma. Hamilton cycles. Random graphs. The probabilistic method. Tree-decompositions, treewidth. The graph minor theorem.

Prerequisite(s): MA 6003 or adviser’s approval.
Weekly Lecture Hours: 3 | Weekly Lab Hours: 0 | Weekly Recitation Hours: 0