CSL851: Algorithmic Graph Theory 

ReferenceTexts Graph Theory by Reinhard Diestel (Chapters 1,2,3,4,5,12) Advanced Graph Algorithms by T.Kloks A course in Combinatorial Optimization by Alexander Schrijver Lecture Notes Graphs and Algorithms, Nikhil Bansal, TU Eindhoven Topics in Combinatorial Optimization, Michel Goemans, MIT Open Courseware Topics in Combinatorial Optimization, Chandra Chekuri, U. of Illinois Graph Theoretic Algorithms, Therese Biedl, U of Waterloo Advanced Topics in Graph Algorithms, Ron Shamir, Tel Aviv U. 

Lecture Date 
Contents 
Additional reading material  Lecture notes from this course 
July 24, 29, 31  Matching: TutteBerge Formula, GallaiEdmonds
Decomposition, Blossoms, Edmonds' Cardinality Algorithm and Proofs of
TutteBerge Formulas and GallaiEdmonds Decomposition,  Notes  Suyash Roongta, Anup Bhatacharya, Khaleeque Ansari 
August 5,7, 12 
Weighted bipartite matching, Edmonds Algorithm for Weighted NonBipartite Matching,Tjoins and applications  Utkarsh Ohm, Ankit Anand, Shubham Gupta 

August 14, 19, 21, 26 
FactorCritical Graphs, Ear Decompositions, Graph orientations, Splitting Off, $k$Connectivity Orientations and Augmentations, Arborescences and Branchings  Komal Bansal, Aarti Soni, MSK Swaroop, Abhinav Kumar 

Sept 4, 10 
Basic Probability 
Nikhil Kumar, Yashoteja Prabhu 

Sep 11 
Hoeffdings inequality and introduction to G(n,p) 
Ashish Gaurav 

Sept 16, 23, 24 
Threshold for connectedness in random graphs 
Siddharth Bora, Devashish Tyagi, Abhishek Gupta 

Oct 9, 14 
Interval Graphs, Chordal Graphs 
Slides  Apoorv Garg, Keshav Choudhary 
Oct 28, 30  Perfect Graphs, Comparabaility graphs  Arpit Jain, Debjyoti Saharoy  
Nov 4, 11, 13  Treewidth, Planar Graphs  Slides  Jatin Batra, Jwala rao, Sushant Saxena 
Nov 18 
Planar Separator Theorem 
Prerequisites, Separators  Ashesh 
Nov 20 
Expanders 
Davis Isaac 

Kuratowski's Theorem  Slides  
Course Evaluation 
The course is in 3 parts with an exam (30 marks) at the end of each part. The lecture scribe is for 10 marks. Click here to download the latex template for the lecture notes. You can find your marks here 

Scribe Schedule 
Please click here to enter your choice for the lecture you want to scribe. 