Graph Theory
Graph Theory. Instructor: Dr. L. Sunil Chandran, Department of Computer Science and Automation, IISc Bangalore. In computer science, graph theory is used extensively. The aim of this course is to introduce the subject of graph theory to computer science students in a thorough way. While the course will cover all elementary concepts such as coloring, covering, hamiltonicity,
planarity, connectivity and so on, it will also introduce the students to some advanced concepts. (from nptel.ac.in)
Covering Problems 
Lecture 01  Introduction: Vertex Cover and Independent Set 
Lecture 02  Matchings: Konig's Theorem and Hall's Theorem 
Lecture 03  More on Hall's Theorem and Some Applications 
Lecture 04  Tutte's Theorem on Existence of a Perfect Matching 
Lecture 05  More on Tutte's Theorem 
Lecture 06  More on Matchings 
Lecture 07  Dominating Set, Path Cover 
Lecture 08  GallaiMilgram Theorem, Dilworth's Theorem 
Connectivity 
Lecture 09  Connectivity: 2Connected and 3Connected Graphs 
Lecture 10  Menger's Theorem 
Lecture 11  More on Connectivity: KLinkedness 
Lecture 12  Minors, Topological Minors and More on KLinkedness 
Coloring 
Lecture 13  Vertex Coloring: Brooks' Theorem 
Lecture 14  More on Vertex Coloring 
Lecture 15  Edge Coloring: Vizing's Theorem 
Lecture 16  Proof of Vizing's Theorem, Introduction to Planarity 
Lecture 17  5Coloring Planar Graphs, Kuratowski's Theorem 
Lecture 18  Proof of Kuratowski's Theorem, List Coloring 
Lecture 19  List Chromatic Index 
Lecture 20  Adjacency Polynomial of a Graph and Combinatorial Nullstellensatz 
Lecture 21  Chromatic Polynomial, KCritical Graphs 
Lecture 22  GallaiRoy Theorem, Acyclic Coloring, Hadwiger Conjecture 
Special Classes of Graphs 
Lecture 23  Perfect Graphs: Examples 
Lecture 24  Interval Graphs, Chordal Graphs 
Lecture 25  Proof of Weak Perfect Graph Theorem (WPGT) 
Lecture 26  Second Proof of WPGT, Some Nonperfect Graph Classes 
Lecture 27  More Special Classes of Graphs 
Lecture 28  Boxicity, Sphericity, Hamiltonian Circuits 
Lecture 29  More on Hamiltonicity: Chvatal's Theorem 
Lecture 30  Chvatal's Theorem, Toughness, Hamiltonicity and 4Color Conjecture 
Network Flows 
Lecture 31  Network Flows: MaxFlow MinCut Theorem 
Lecture 32  More on Network Flows: Circulations 
Lecture 33  Circulations and Tensions 
Lecture 34  More on Circulations and Tensions, Flow Number and Tutte's Flow Conjectures 
Random Graphs and Probabilistic Method 
Lecture 35  Random Graphs and Probabilistic Method: Preliminaries 
Lecture 36  Probabilistic Method: Markov's Inequality, Ramsey Number 
Lecture 37  Probabilistic Method: Graphs of High Girth and High Chromatic Number 
Lecture 38  Probabilistic Method: Second Moment Method, Lovasz Local Lemma 
Graph Minors 
Lecture 39  Graph Minors and Hadwiger Conjecture 
Lecture 40  More on Graph Minors, Tree Decompositions 
References 
Graph Theory
Instructor: Dr. L. Sunil Chandran, Department of Computer Science and Automation, IISc Bangalore. An introduction to the subject of graph theory.
