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.
Sl.No.
Topics
No.of Hours
1
Vertex Cover
1
2
Matchings
3
3
Pathcover
1
4
Connectivity
3
5
Hamiltonicity
3
6
Vertex Coloring
4
7
Edge Coloring
3
8
Other Coloring Problems
2
9
Perfect graphs
2
10
Planar graphs
3
11
Other special classes of graphs
2
12
Network flow
3
13
Introduction to minor theory
3
14
Probabilistic Methods: Basics
3
15
Markov, Chebishey Inequalities
1
16
Lovasz Local Lemma
2
17
Random graph
1
Total
40
R. Diestel, "Graph Theory", Springer-Verlag, 2nd edition, 2000.
N. Alon and J. Spenser, "Probabilistic Methods", John Wiley and Sons, 2nd
edition, 2000.
Important: Please enable javascript in your browser and download Adobe Flash player to view this site
Site Maintained by Web Studio, IIT Madras. Contact Webmaster: nptel@iitm.ac.in
