Media Storage Type : 32 GB USB Stick
NPTEL Subject Matter Expert : Dr. L. Sunil Chandran
NPTEL Co-ordinating Institute : IISc Bangalore
NPTEL Lecture Count : 40
NPTEL Course Size : 19 GB
NPTEL PDF Text Transcription : Available and Included
NPTEL Subtitle Transcription : Available and Included (SRT)
Lecture Titles:
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