Graph Theory For Computer Scientists
Spring 2009
International Insitute of Information Technology, Hyderabad, India.

Course Instructor: Kishore Kothapalli

kkishore@mail.iiit.ac.in
Office Hours: Tuesday, Thursday: 4:00 PM -- 5:00 PM

TAs

• Bharat Joshi bharatj@research.iiit.ac.in
• N.Pradeep Rajiv pradeepr@research.iiit.ac.in

Course Topics

A tentative list of topics covered in the course will be as follows: The exact order and contents are subject to change.

1. Introduction - Notation, degree sequences
2. Connectivity - Definitions, SCC, Bi-connected Components
3. Trees and Euler Graphs - Characterization, Counting Trees Cayleys Formula, Counting Binary Trees
4. Bipartite Graphs - Randomness and Large Bipartite Subgraph
5. Matching - Definitions, Hall's theorem, Stable matchings and the Marriage theorem
6. Graph Coloring - Definitions ,Greedy Algorithm,Interval graph Coloring, Counting K Colorings,Mycielski's Construction,Chordal Graphs
7. Network Flows - Flow, Ford-Fulkerson, Edmonds-Karp, Connections to Bipartite Matching
8. Planar Graphs - Definition, Characterization, Coloring
9. Algebraic Graph Theory - Eigenvalues of Graphs, Connection To Graph Properties
10. Random Walks on Graphs -Markov Chains, Convergence to Stationarity

Homeworks

• Homework 1 (Also in PDF)
• Homework 2 (Also in PDF)
• Homework 3 (Also in PDF)
• Homework 5 (Also in PDF)
• Homework 6 (Also in PDF)
• Homework 7 (Also in PDF)

Grading Scheme

• Homeworks -- 20 %
• Midexam 1 -- 20 %
• Midexam 2 -- 20 %
• Endexam -- 40%

Reference Books

1. Douglas B. West, Introduction to Graph Theory.
2. Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 2nd edition.