2013-2014 Undergraduate and Graduate Bulletin (with addenda) 
    
    Nov 12, 2018  
2013-2014 Undergraduate and Graduate Bulletin (with addenda) [ARCHIVED CATALOG]

[Add to Portfolio]

MA-GY 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, 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



[Add to Portfolio]