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
Course Lectures