# 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