NPTEL : Graph Theory (Computer Science and Engineering)

Co-ordinators : Dr. L. Sunil Chandran


Lecture 1 - Introduction: Vertex cover and independent set

Lecture 2 - Matchings: Konig’s theorem and Hall’s theorem

Lecture 3 - More on Hall’s theorem and some applications

Lecture 4 - Tutte’s theorem on existence of a perfect matching

Lecture 5 - More on Tutte’s theorem

Lecture 6 - More on Matchings

Lecture 7 - Dominating set, path cover

Lecture 8 - Gallai – Millgram theorem, Dilworth’s theorem

Lecture 9 - Connectivity: 2-connected and 3-connected graphs

Lecture 10 - Menger’s theorem

Lecture 11 - More on connectivity: k- linkedness

Lecture 12 - Minors, topological minors and more on k- linkedness

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 - 5- coloring planar graphs, Kuratowsky’s theorem

Lecture 18 - Proof of Kuratowsky’s theorem, List coloring

Lecture 19 - List chromatic index

Lecture 20 - Adjacency polynomial of a graph and combinatorial Nullstellensatz

Lecture 21 - Chromatic polynomial, k - critical graphs

Lecture 22 - Gallai-Roy theorem, Acyclic coloring, Hadwiger’s conjecture

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 non-perfect 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 4-color conjecture

Lecture 31 - Network flows: Max flow 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

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

Lecture 39 - Graph minors and Hadwiger’s conjecture

Lecture 40 - More on graph minors, tree decompositions