CS6240-2023
Structural Graph Theory

Syllabus:

• Module-0: Preliminaries (1 week)
  Isomorphisms & Automorphisms; Subgraphs & Supergraphs; Paths & Cycles; Connectedness; Special Graph Families; Connections with Complexity & Algorithms; Bipartiteness; Eulerian tours vs Hamiltonian cycles

• Module-1: Cycle Space & Bond Space (1.5 weeks)
  Cycles & Even Subgraphs; The Cycle Space; Orthogonality; Orthogonal Complement; Cuts & Bonds; The Bond Space

• Module-2: Connectivity (3.5 weeks)
  Nonseparable graphs; Block & Ear Decompositions; Vertex & edge Connectivity; Menger's Theorems; Dirac's Theorem; edge contraction; 3-connected graphs; Thomassen's Theorem & Tutte's Wheel Theorem

• Module-3: Planarity (3 weeks)
  Planarity & the Jordan Curve Theorem; containment notions; Kuratowski vs Wagner; Faces, Plane Duality & Nonseparability; Euler's formula & its implications; Tutte's Theory of Bridges; Planarity Testing; Nonseparating cycles & 3-connectedness

• Module-4: Colorings(2 weeks)
  Brief history of the 4 Color Problem; 5 Color Theorem & Heawood's Proof; Edge Colorings & Matchings; Tait's Formulation of the 4 Color Problem; Tait's Theorem; Chromatic Number & Bounds; Greedy Heuristic; Brooks' Theorem

• Module-5: Matchings (3 weeks)
  Alternating paths/cycles & Augmenting paths; Berge's Theorem; Bipartite Matchings, Hall's & Konig-Egervary Theorems; Edge Colorings, Vizing's Theorem & Snarks; Barriers; Tutte-Berge Formula & Tutte's Theorem; Petersen's Theorem