Advanced Graph Theory focuses on problem solving
using the most important notions of graph theory with an in-depth
study of concepts on the applications in the field of computer
science. This course provides an in-depth understanding of Graphs
and fundamental principles and models underlying the theory,
algorithms, and proof techniques in the field of Graph Theory.
Emerging applications of Graph Theory in Computer Science domain
will be covered for significant impact. Upon completing this course,
students will have intimate knowledge about how the graph theory
play an important role to solve the technology driven and research
oriented problems.

Week

Topics

1.

Introduction to Graphs & its Applications,
Basics of Paths, Cycles, and Trails, Connection,
Bipartite Graphs, Eulerian Circuits, Vertex Degrees and
Counting, Degree-sum formula, The Chinese Postman
Problem and Graphic Sequences.

2.

Trees and Distance, Properties of Trees, Spanning Trees
and Enumeration, Matrix-tree computation, Cayley's
Formula, Prufer code.

3.

Matchings and Covers,
Hall's Condition, Min-Max Theorem, Independent Sets,
Covers and Maximum Bipartite Matching, Augmenting Path
Algorithm, Weighted Bipartite Matching, Hungarian
Algorithm.

4.

Stable Matchings and Faster Bipartite Matching, Factors
& Perfect Matching in General Graphs, Matching in
General Graphs: Edmonds’ Blossom Algorithm

5.

Connectivity and Paths: Cuts and Connectivity, k-Connected
Graphs, Network Flow Ford-Fulkerson Labeling Algorithm,
Max-Flow Min-cut Theorem, Menger's Proof using Max-Flow
Min-Cut Theorem.

6.

Vertex Coloring and Upper Bounds, Brooks’ Theorem and
Color-Critical Graphs, Counting Proper Colorings.

7.

Planar Graphs, Characterization of Planar Graphs,
Kuratowski's Theorem, Wagner's Theorem.

8.

Line Graphs and
Edge-coloring, Hamiltonian Graph, Traveling Salesman
Problem and NP-Completeness, Dominating Sets.

Discrete Mathematics

D.B. West, Introduction to Graph Theory, Prentice Hall, 2001

Jon Kleinberg and Eva Tardos, Algorithm Design, Addison-Wesley, 2005

J.A.Bondy and U.S.R.Murty: Graph Theory, Springer, 2008.

C. Berge: Graphs and Hypergraphs, North Holland/Elsevier, (1973)

nil

nil

Important: Please enable javascript in your browser and download Adobe Flash player to view this site
Site Maintained by Web Studio, IIT Madras. Contact Webmaster: nptel@iitm.ac.in