|
Course

# Graph Theory

Indian Institute of Science Bangalore

In computer science, graph theory is used extensively. The intension of this course is to introduce the subject of graph theory to computer science students in a thorough way. While the course will cover all elementary concepts such as coloring, covering, hamiltonicity, planarity, connectivity and so on, it will also introduce the students to some advanced concepts.

Course topics:

1. Vertex Cover
2. Matchings
3. Pathcover
4. Connectivity
5. Hamiltonicity
6. Vertex Coloring
7. Edge Coloring
8. Other Coloring Problems
9. Perfect graphs
10. Planar graphs
11. Other special classes of graphs
12. Network flow
13. Introduction to minor theory
14. Probabilistic Methods: Basics
15. Markov, Chebishey Inequalities
16. Lovasz Local Lemma
17. Random graph
Home > Computer Science > Theoretical Computer Science > Graph TheoryLectures:
• ### Mod-01 Lec-01 Introduction: Vertex cover and independent set

00:56:13Dr. L. Sunil Chandran
• ### Mod-01 Lec-02 Matchings: Konig's theorem and Hall's theorem

00:58:27Dr. L. Sunil Chandran
• ### Mod-01 Lec-03 More on Hall's theorem and some applications

00:57:38Dr. L. Sunil Chandran
• ### Mod-01 Lec-04 Tutte's theorem on existence of a perfect matching

00:58:07Dr. L. Sunil Chandran
• ### Mod-01 Lec-05 More on Tutte's theorem

00:58:10Dr. L. Sunil Chandran
• ### Mod-01 Lec-06 More on Matchings

00:57:58Dr. L. Sunil Chandran
• ### Mod-01 Lec-07 Dominating set, path cover

00:58:45Dr. L. Sunil Chandran
• ### Mod-01 Lec-08 Gallai -- Millgram theorem, Dilworth's theorem

00:57:51Dr. L. Sunil Chandran
• ### Mod-02 Lec-09 Connectivity: 2-connected and 3- connected graphs

00:58:03Dr. L. Sunil Chandran
• ### Mod-02 Lec-10 Menger's theorem

00:56:17Dr. L. Sunil Chandran
• ### Mod-02 Lec-11 More on connectivity: k- linkedness

00:55:28Dr. L. Sunil Chandran
• ### Mod-02 Lec-12 Minors, topological minors and more on k- linkedness

00:55:33Dr. L. Sunil Chandran
• ### Mod-03 Lec-13 Vertex coloring: Brooks theorem

00:57:21Dr. L. Sunil Chandran
• ### Mod-03 Lec-14 More on vertex coloring

00:55:34Dr. L. Sunil Chandran
• ### Mod-03 Lec-15 Edge coloring: Vizing's theorem

00:56:36Dr. L. Sunil Chandran
• ### Mod-03 Lec-16 Proof of Vizing's theorem, Introduction to planarity

00:56:52Dr. L. Sunil Chandran
• ### Mod-03 Lec-17 5- coloring planar graphs, Kuratowsky's theorem

00:57:32Dr. L. Sunil Chandran
• ### Mod-03 Lec-18 Proof of Kuratowsky's theorem, List coloring

00:56:48Dr. L. Sunil Chandran
• ### Mod-03 Lec-19 List chromatic index

00:57:37Dr. L. Sunil Chandran
• ### Mod-03 Lec-20 Adjacency polynomial of a graph and combinatorial Nullstellensatz

00:56:30Dr. L. Sunil Chandran
• ### Mod-03 Lec-21 Chromatic polynomial, k - critical graphs

00:57:07Dr. L. Sunil Chandran
• ### Mod-03 Lec-22 Gallai-Roy theorem, Acyclic coloring, Hadwiger's conjecture

00:54:03Dr. L. Sunil Chandran
• ### Mod-04 Lec-23 Perfect graphs: Examples

00:57:24Dr. L. Sunil Chandran
• ### Mod-04 Lec-24 Interval graphs, chordal graphs

00:57:08Dr. L. Sunil Chandran
• ### Mod-04 Lec-25 Proof of weak perfect graph theorem (WPGT)

00:56:35Dr. L. Sunil Chandran
• ### Mod-04 Lec-26 Second proof of WPGT, Some non-perfect graph classes

00:57:48Dr. L. Sunil Chandran
• ### Mod-04 Lec-27 More special classes of graphs

00:57:38Dr. L. Sunil Chandran
• ### Mod-04 Lec-28 Boxicity,Sphericity, Hamiltonian circuits

00:57:02Dr. L. Sunil Chandran
• ### Mod-04 Lec-29 More on Hamiltonicity: Chvatal's theorem

00:57:36Dr. L. Sunil Chandran
• ### Mod-04 Lec-30 Chvatal's theorem, toughness, Hamiltonicity and 4-color conjecture

00:59:00Dr. L. Sunil Chandran
• ### Mod-05 Lec-31 Network flows: Max flow mincut theorem

00:57:52Dr. L. Sunil Chandran
• ### Mod-05 Lec-32 More on network flows: Circulations

00:58:35Dr. L. Sunil Chandran
• ### Mod-05 Lec-33 Circulations and tensions

00:58:20Dr. L. Sunil Chandran
• ### Mod-05 Lec-34 More on circulations and tensions, flow number and Tutte's flow conjectures

00:56:50Dr. L. Sunil Chandran
• ### Mod-06 Lec-35 Random graphs and probabilistic method: Preliminaries

00:57:25Dr. L. Sunil Chandran
• ### Mod-06 Lec-36 Probabilistic method: Markov's inequality, Ramsey number

00:57:34Dr. L. Sunil Chandran
• ### Mod-06 Lec-37 Probabilistic method: Graphs of high girth and high chromatic number

00:58:20Dr. L. Sunil Chandran
• ### Mod-06 Lec-38 Probabilistic method: Second moment method, Lovasz local lemma

00:58:50Dr. L. Sunil Chandran
• ### Mod-07 Lec-39 Graph minors and Hadwiger's conjecture

00:58:28Dr. L. Sunil Chandran
• ### Mod-07 Lec-40 More on graph minors, tree decompositions

00:58:31Dr. L. Sunil Chandran
Course Material: