# 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
• ##### Mod-01 Lec-01 Introduction: Vertex cover and independent set
Dr. L. Sunil Chandran
• ##### Mod-01 Lec-02 Matchings: Konig&#39;s theorem and Hall&#39;s theorem
Dr. L. Sunil Chandran
• ##### Mod-01 Lec-03 More on Hall&#39;s theorem and some applications
Dr. L. Sunil Chandran
• ##### Mod-01 Lec-04 Tutte&#39;s theorem on existence of a perfect matching
Dr. L. Sunil Chandran
• ##### Mod-01 Lec-05 More on Tutte&#39;s theorem
Dr. L. Sunil Chandran
• ##### Mod-01 Lec-06 More on Matchings
Dr. L. Sunil Chandran
• ##### Mod-01 Lec-07 Dominating set, path cover
Dr. L. Sunil Chandran
• ##### Mod-01 Lec-08 Gallai -- Millgram theorem, Dilworth&#39;s theorem
Dr. L. Sunil Chandran
• ##### Mod-02 Lec-09 Connectivity: 2-connected and 3- connected graphs
Dr. L. Sunil Chandran
• ##### Mod-02 Lec-10 Menger&#39;s theorem
Dr. L. Sunil Chandran
• ##### Mod-02 Lec-11 More on connectivity: k- linkedness
Dr. L. Sunil Chandran
• ##### Mod-02 Lec-12 Minors, topological minors and more on k- linkedness
Dr. L. Sunil Chandran
• ##### Mod-03 Lec-13 Vertex coloring: Brooks theorem
Dr. L. Sunil Chandran
• ##### Mod-03 Lec-14 More on vertex coloring
Dr. L. Sunil Chandran
• ##### Mod-03 Lec-15 Edge coloring: Vizing&#39;s theorem
Dr. L. Sunil Chandran
• ##### Mod-03 Lec-16 Proof of Vizing&#39;s theorem, Introduction to planarity
Dr. L. Sunil Chandran
• ##### Mod-03 Lec-17 5- coloring planar graphs, Kuratowsky&#39;s theorem
Dr. L. Sunil Chandran
• ##### Mod-03 Lec-18 Proof of Kuratowsky&#39;s theorem, List coloring
Dr. L. Sunil Chandran
• ##### Mod-03 Lec-19 List chromatic index
Dr. L. Sunil Chandran
• ##### Mod-03 Lec-20 Adjacency polynomial of a graph and combinatorial Nullstellensatz
Dr. L. Sunil Chandran
• ##### Mod-03 Lec-21 Chromatic polynomial, k - critical graphs
Dr. L. Sunil Chandran
• ##### Mod-03 Lec-22 Gallai-Roy theorem, Acyclic coloring, Hadwiger&#39;s conjecture
Dr. L. Sunil Chandran
• ##### Mod-04 Lec-23 Perfect graphs: Examples
Dr. L. Sunil Chandran
• ##### Mod-04 Lec-24 Interval graphs, chordal graphs
Dr. L. Sunil Chandran
• ##### Mod-04 Lec-25 Proof of weak perfect graph theorem (WPGT)
Dr. L. Sunil Chandran
• ##### Mod-04 Lec-26 Second proof of WPGT, Some non-perfect graph classes
Dr. L. Sunil Chandran
• ##### Mod-04 Lec-27 More special classes of graphs
Dr. L. Sunil Chandran
• ##### Mod-04 Lec-28 Boxicity,Sphericity, Hamiltonian circuits
Dr. L. Sunil Chandran
• ##### Mod-04 Lec-29 More on Hamiltonicity: Chvatal&#39;s theorem
Dr. L. Sunil Chandran
• ##### Mod-04 Lec-30 Chvatal&#39;s theorem, toughness, Hamiltonicity and 4-color conjecture
Dr. L. Sunil Chandran
• ##### Mod-05 Lec-31 Network flows: Max flow mincut theorem
Dr. L. Sunil Chandran
• ##### Mod-05 Lec-32 More on network flows: Circulations
Dr. L. Sunil Chandran
• ##### Mod-05 Lec-33 Circulations and tensions
Dr. L. Sunil Chandran
• ##### Mod-05 Lec-34 More on circulations and tensions, flow number and Tutte&#39;s flow conjectures
Dr. L. Sunil Chandran
• ##### Mod-06 Lec-35 Random graphs and probabilistic method: Preliminaries
Dr. L. Sunil Chandran
• ##### Mod-06 Lec-36 Probabilistic method: Markov&#39;s inequality, Ramsey number
Dr. L. Sunil Chandran
• ##### Mod-06 Lec-37 Probabilistic method: Graphs of high girth and high chromatic number
Dr. L. Sunil Chandran
• ##### Mod-06 Lec-38 Probabilistic method: Second moment method, Lovasz local lemma
Dr. L. Sunil Chandran
• ##### Mod-07 Lec-39 Graph minors and Hadwiger&#39;s conjecture
Dr. L. Sunil Chandran
• ##### Mod-07 Lec-40 More on graph minors, tree decompositions
Dr. L. Sunil Chandran