2013-2014 Undergraduate and Graduate Catalog (without addenda) 
    
    Mar 29, 2024  
2013-2014 Undergraduate and Graduate Catalog (without addenda) [ARCHIVED CATALOG]

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