Graph Theory

Department: 
MATH
Course Number: 
6014
Hours - Lecture: 
3
Hours - Lab: 
0
Hours - Recitation: 
0
Hours - Total Credit: 
3
Typical Scheduling: 
Every fall semester

Fundamentals, connectivity, matchings, colorings, extremal problems, Ramsey theory, planar graphs, perfect graphs. Applications to operations research and the design of efficient algorithms.

Prerequisites: 

MATH 4022

Course Text: 

Text at the level of Diestel, Graph Theory

Topic Outline: 
  • Fundamentals
    • Isomorphism, paths, cycles, trees, spanning trees, Eulerian and Hamiltonian graphs
  • Connectivity
    • Max-flow Min-cut theorem, Menger's theorem, the structure of 1-, 2-, 3-connected graphs (blocks, ear-decomposition, contractible edges, Tutte's synthesis of 3-connected graphs)
  • Matchings
    • Hall's theorem, systems of distinct representatives, Tutte's 1-factor theorem, Edmonds' matching algorithm, Dilworth's theorem, the matching polytope, the Chinese postman problem
  • Coloring
    • Greedy coloring, Brooks' theorem, chromatic polynomial, highly chromatic graphs of large girth, Vizing's theorem, Erdos-de Bruijn compactness theorem
  • Extremal problems
    • Turan's theorem, the problem of Zarankiewicz
  • Ramsey's theory
    • Ramsey's theorem, applications
  • Planar graphs
    • Euler's formula, dual graphs, Kuratowski's theorem, 5-color theorem, equivalents of the 4-color theorem, graphs on surfaces
  • Perfect graphs
    • Classes of perfect graphs (bipartite, comparability graphs, line graphs of bipartite graphs, chordal graphs, complements of the above), the Perfect Graph Theorem
  • Random graphs
    • Lower bound for Ramsey numbers, highly chromatic graphs of large girth, properties of random graphs such as the number of edges, chromatic number, the clique number, connectivity, subgraphs, threshold functions, 0-1 law