NPTEL : NOC:Advanced Graph Theory (Computer Science and Engineering)

Co-ordinators : Dr.Rajiv Misra


Lecture 1 - Graph Theory: Introduction

Lecture 2 - Paths, Cycles and Trails

Lecture 3 - Eulerian Circuits, Vertex Degrees and Counting

Lecture 4 - The Chinese Postman Problem and Graphic Sequences

Lecture 5 - Trees and Distance

Lecture 6 - Spanning Trees and Enumeration

Lecture 7 - Matchings and Covers

Lecture 8 - Independent Sets, Covers and Maximum Bipartite Matching

Lecture 9 - Weighted Bipartite Matching

Lecture 10 - Stable Matchings and Faster Bipartite Matching

Lecture 11 - Factors and Perfect Matching in General Graphs

Lecture 12 - Matching in General Graphs: Edmonds’ Blossom Algorithm

Lecture 13 - Connectivity and Paths: Cuts and Connectivity

Lecture 14 - k-Connected Graphs

Lecture 15 - Network Flow Problems

Lecture 16 - Vertex Coloring and Upper Bounds

Lecture 17 - Brooks’ Theorem and Color-Critical Graphs

Lecture 18 - Counting Proper Colorings

Lecture 19 - Planar Graphs

Lecture 20 - Characterization of Planar Graphs

Lecture 21 - Line Graphs and Edge-coloring

Lecture 22 - Hamiltonian Graph, Traveling Salesman Problem and NP-Completeness

Lecture 23 - Connected Dominating Set and Distributed Algorithm