|
|
|
Jan 15, 2025
|
|
2014-2016 Undergraduate and Graduate Bulletin (without addenda) [ARCHIVED CATALOG]
|
MA-GY 6103 Graph Theory3 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, list coloring. 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-GY 6003 or adviser’s approval.
Weekly Lecture Hours: 3 | Weekly Lab Hours: 0 | Weekly Recitation Hours: 0
|
|
|
