IISc Bangalore · Computer Science

Graph Theory

Dr. L. Sunil Chandran · 40 free video lectures

40 video lectures. Topics: Introduction: Vertex cover and independent set; Matchings: Konigs theorem and Halls theorem; More on Halls theorem and some applications; Tuttes theorem on existence of a perfect matching; More on Tuttes theorem; More on Matchings; Dominating set, path cover; Gallai…

▶ Play on Open Lecture HallCourse page ↗

Lectures

  1. Introduction: Vertex cover and independent set
  2. Matchings: Konigs theorem and Halls theorem
  3. More on Halls theorem and some applications
  4. Tuttes theorem on existence of a perfect matching
  5. More on Tuttes theorem
  6. More on Matchings
  7. Dominating set, path cover
  8. Gallai : Millgram theorem, Dilworths theorem
  9. Connectivity: 2-connected and 3- connected graphs
  10. Mengers 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: Vizings theorem
  16. Proof of Vizings theorem, Introduction to planarity
  17. 5- coloring planar graphs, Kuratowskys theorem
  18. Proof of Kuratowskys 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, Hadwigers 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: Chvatals theorem
  30. Chvatals 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 Tuttes flow conjectures
  35. Random graphs and probabilistic method: Preliminaries
  36. Probabilistic method: Markovs 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 Hadwigers conjecture
  40. More on graph minors, tree decompositions

From NPTEL (IITs and IISc) · CC BY-NC-SA. More from IISc Bangalore.

Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights