Graph Theory

IISc Bangalore Course , Prof. L. Sunil Chandran

Lecture 1: Introduction: Vertex cover and independent set

Download:    MP4,FLV & 3GP
Lecture Details :

Graph Theory by Dr. L. Sunil Chandran, Department of Computer Science and Automation, IISc Bangalore. For more details on NPTEL visit

Course Description :

Introduction:Vertex cover and independent set - Matchings: Konig's theorem and Hall's theorem - More on Hall's theorem and some applications - Tutte's theorem on existence of a perfect matching - More on Tutte's theorem - More on Matchings - Dominating set, path cover - Gallai -- Millgram theorem, Dilworth's theorem - Connectivity: 2-connected and 3- connected graphs-Menger's theorem - More on connectivity: k- linkedness - Minors, topological minors and more on k- linkedness-Vertex coloring: Brooks theorem - More on vertex coloring - Edge coloring: Vizing's theorem - proof of Vizing's theorem, Introduction to planarity - coloring planar graphs, Kuratowsky's theorem-Proof of Kuratowsky's theorem, List coloring

List chromatic index - Adjacency polynomial of a graph and combinatorial Nullstellensatz - Chromatic polynomial, k - critical graphs - Gallai-Roy theorem, Acyclic coloring, Hadwiger's conjecture - Perfect graphs: Examples - interval graphs, chordal graphs - Proof of weak perfect graph theorem (WPGT) - Second proof of WPGT, Some non-perfect graph classes-More special classes of graphs - Boxicity,Sphericity, Hamiltonian circuits - More on Hamiltonicity: Chvatal's theorem - Chvatal's theorem, toughness, Hamiltonicity and 4-color conjecture - Network flows: Max flow mincut theorem - More on network flows: Circulations - Circulations and tensions - More on circulations and tensions, flow number and Tutte's flow conjectures - Ran Probabilistic method: Markov's inequality, Ramsey number - Probabilistic method: Graphs of high girth and high chromatic number,Second moment method, Lovasz local lemma, Graph minors and Hadwiger's conjecture - More on graph minors, tree decompositions

Other Resources

These lecture videos are delivered by IISc Bangalore, under the NPTEL program, lot of nptel video courses are available for learning online.

COURSE Reviews

5 Stars 12
4 Stars 10
3 Stars 1
2 Stars 4
1 Stars 9
3.3 Overall Ratings