# Graph Theory

- Institution: IISc Bangalore
- Department: Computer Science and Engineering
- Teacher: Dr. L. Sunil Chandran
- Level: Undergraduate
- Language: English
- Subjects: Computer science, Engineering
- Source: [NPTEL](https://nptel.ac.in/courses/106108054)
- Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.)
- Syllabus: [at the source](https://nptel.ac.in/courses/106108054)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

## Lectures

1. [Introduction: Vertex cover and independent set](https://invisiblenetwork.ai/learn/nptel/106108054/8b17d7b16a5f) (Video)
2. [Matchings: Konigs theorem and Halls theorem](https://invisiblenetwork.ai/learn/nptel/106108054/862164a1eb8c) (Video)
3. [More on Halls theorem and some applications](https://invisiblenetwork.ai/learn/nptel/106108054/ece09da4dbb5) (Video)
4. [Tuttes theorem on existence of a perfect matching](https://invisiblenetwork.ai/learn/nptel/106108054/8b12e45dfe83) (Video)
5. [More on Tuttes theorem](https://invisiblenetwork.ai/learn/nptel/106108054/840205094807) (Video)
6. [More on Matchings](https://invisiblenetwork.ai/learn/nptel/106108054/0575c28d6097) (Video)
7. [Dominating set, path cover](https://invisiblenetwork.ai/learn/nptel/106108054/8eef325a48e8) (Video)
8. [Gallai : Millgram theorem, Dilworths theorem](https://invisiblenetwork.ai/learn/nptel/106108054/7e509033d03e) (Video)
9. [Connectivity: 2-connected and 3- connected graphs](https://invisiblenetwork.ai/learn/nptel/106108054/a059e132cc2d) (Video)
10. [Mengers theorem](https://invisiblenetwork.ai/learn/nptel/106108054/777a011b68f4) (Video)
11. [More on connectivity: k- linkedness](https://invisiblenetwork.ai/learn/nptel/106108054/06bab51cc4b5) (Video)
12. [Minors, topological minors and more on k- linkedness](https://invisiblenetwork.ai/learn/nptel/106108054/e56016d84dea) (Video)
13. [Vertex coloring: Brooks theorem](https://invisiblenetwork.ai/learn/nptel/106108054/786e3c57ccac) (Video)
14. [More on vertex coloring](https://invisiblenetwork.ai/learn/nptel/106108054/686f98ad2074) (Video)
15. [Edge coloring: Vizings theorem](https://invisiblenetwork.ai/learn/nptel/106108054/659326e3e598) (Video)
16. [Proof of Vizings theorem, Introduction to planarity](https://invisiblenetwork.ai/learn/nptel/106108054/47eb1800ba24) (Video)
17. [5- coloring planar graphs, Kuratowskys theorem](https://invisiblenetwork.ai/learn/nptel/106108054/0c29aaa5c8d3) (Video)
18. [Proof of Kuratowskys theorem, List coloring](https://invisiblenetwork.ai/learn/nptel/106108054/39baafb41bb2) (Video)
19. [List chromatic index](https://invisiblenetwork.ai/learn/nptel/106108054/169718c5cdd4) (Video)
20. [Adjacency polynomial of a graph and combinatorial Nullstellensatz](https://invisiblenetwork.ai/learn/nptel/106108054/d37161b5b886) (Video)
21. [Chromatic polynomial, k - critical graphs](https://invisiblenetwork.ai/learn/nptel/106108054/46c00533d7f4) (Video)
22. [Gallai-Roy theorem, Acyclic coloring, Hadwigers conjecture](https://invisiblenetwork.ai/learn/nptel/106108054/ab306ed57842) (Video)
23. [Perfect graphs: Examples](https://invisiblenetwork.ai/learn/nptel/106108054/6be49c87d9ec) (Video)
24. [Interval graphs, chordal graphs](https://invisiblenetwork.ai/learn/nptel/106108054/e2dad7d56082) (Video)
25. [Proof of weak perfect graph theorem (WPGT)](https://invisiblenetwork.ai/learn/nptel/106108054/9fd388b106d9) (Video)
26. [Second proof of WPGT, Some non-perfect graph classes](https://invisiblenetwork.ai/learn/nptel/106108054/a8dd443e61ff) (Video)
27. [More special classes of graphs](https://invisiblenetwork.ai/learn/nptel/106108054/bdadedd7ff34) (Video)
28. [Boxicity,Sphericity, Hamiltonian circuits](https://invisiblenetwork.ai/learn/nptel/106108054/661532ac72b6) (Video)
29. [More on Hamiltonicity: Chvatals theorem](https://invisiblenetwork.ai/learn/nptel/106108054/0d0035d46b30) (Video)
30. [Chvatals theorem, toughness, Hamiltonicity and 4-color conjecture](https://invisiblenetwork.ai/learn/nptel/106108054/82e5edafff50) (Video)
31. [Network flows: Max flow mincut theorem](https://invisiblenetwork.ai/learn/nptel/106108054/bce5b012999e) (Video)
32. [More on network flows: Circulations](https://invisiblenetwork.ai/learn/nptel/106108054/06b7644366fa) (Video)
33. [Circulations and tensions](https://invisiblenetwork.ai/learn/nptel/106108054/966f049e7ca8) (Video)
34. [More on circulations and tensions, flow number and Tuttes flow conjectures](https://invisiblenetwork.ai/learn/nptel/106108054/bcdbdcb86ab0) (Video)
35. [Random graphs and probabilistic method: Preliminaries](https://invisiblenetwork.ai/learn/nptel/106108054/9db65b330c43) (Video)
36. [Probabilistic method: Markovs inequality, Ramsey number](https://invisiblenetwork.ai/learn/nptel/106108054/b165c92df19a) (Video)
37. [Probabilistic method: Graphs of high girth and high chromatic number](https://invisiblenetwork.ai/learn/nptel/106108054/a6b34d035ec2) (Video)
38. [Probabilistic method: Second moment method, Lovasz local lemma](https://invisiblenetwork.ai/learn/nptel/106108054/bee2bcbe871c) (Video)
39. [Graph minors and Hadwigers conjecture](https://invisiblenetwork.ai/learn/nptel/106108054/48ffd865a0ec) (Video)
40. [More on graph minors, tree decompositions](https://invisiblenetwork.ai/learn/nptel/106108054/f179a09707e1) (Video)