Graph Theory Video Lectures

Graph Theory
'Graph Theory' Video Lectures by Dr. L. Sunil Chandran from IISc Bangalore
"Graph Theory" - Video Lectures
1. Introduction: Vertex cover and independent set
2. Matchings: Konig’s theorem and Hall’s theorem
3. More on Hall’s theorem and some applications
4. Tutte’s theorem on existence of a perfect matching
5. More on Tutte’s theorem
6. More on Matchings
7. Dominating set, path cover
8. Gallai – Millgram theorem, Dilworth’s theorem
9. Connectivity: 2-connected and 3- connected graphs
10. Menger’s theorem
11. More on connectivity: k- linkedness
12. Minors, topological minors and more on k- linkedness
13. Vertex coloring: Brooks theorem
14. More on vertex coloring
15. Edge coloring: Vizing’s theorem
16. Proof of Vizing’s theorem, Introduction to planarity
17. 5- coloring planar graphs, Kuratowsky’s theorem
18. Proof of Kuratowsky’s theorem, List coloring
19. List chromatic index
20. Adjacency polynomial of a graph and combinatorial Nullstellensatz
21. Chromatic polynomial, k - critical graphs
22. Gallai-Roy theorem, Acyclic coloring, Hadwiger’s conjecture
23. Perfect graphs: Examples
24. Interval graphs, chordal graphs
25. Proof of weak perfect graph theorem (WPGT)
26. Second proof of WPGT, Some non-perfect graph classes
27. More special classes of graphs
28. Boxicity,Sphericity, Hamiltonian circuits
29. More on Hamiltonicity: Chvatal’s theorem
30. Chvatal’s theorem, toughness, Hamiltonicity and 4-color conjecture
31. Network flows: Max flow mincut theorem
32. More on network flows: Circulations
33. Circulations and tensions
34. More on circulations and tensions, flow number and Tutte’s flow conjectures
35. Random graphs and probabilistic method: Preliminaries
36. Probabilistic method: Markov’s inequality, Ramsey number
37. Probabilistic method: Graphs of high girth and high chromatic number
38. Probabilistic method: Second moment method, Lovasz local lemma
39. Graph minors and Hadwiger’s conjecture
40. More on graph minors, tree decompositions
Search Courses
NPTELVideos.com