F E E D B A C K

MTH310 - Graph Theory

IIIT-Delhi

Winter 2020

4 credits

Instructor

Samaresh Chatterji

Teaching Assistants

Anurag Goel
KARAMJEET SINGH

Info - Graph Theory, IIIT-Delhi

Overview

This course is aimed at giving students an introduction to the theory of graphs. The course will introduce concepts that are widely used such as matchings, colorings, etc and study relations between various graph parameters such as matching number, chromatic number, clique number, etc. The emphasis will be on common proof techniques, and applying them to prove properties of graphs in general and for specific families of graphs.
 

Description

CO1: Know elementary structural properties and be able to evaluate them for some simple graph classes   CO2:  Know about fundamental graph parameters and be able to calculate them for graph classes  CO3: Know about connectivity, matchings, cuts and flows, coloring, planarity CO4: Write simple proofs based on the properties of the graphs and stabdard  theorems

Evaluation

valuation: One test (10%), mid-semester exam (20%), weekly tutorial submissions and occasional quizzes (30%), end-semester exam (40%). Weightage of the above components may be adjusted by not more than 5%.
 
Grading: A – 75%, B – 60%, C – 45%, D – 30%. These cut-off points may be adjusted by not more than 5%.  
 

Pre-requisites

Prerequisites (Desirable): Linear Algebra (MTH100), Discrete Mathematics (CSE121) or Discrete Structures (MTH210)

Class Timings

Timetable:
Lectures: Mon, Thu: 16:00 to 17:30 (C02)
Tutorial: Tue: 09:00 to 10:30 (C12, C13)

Office Hours

Instructor - Samaresh Chatterji email - samaresh@iiitd.ac.in Office Hours: 2:00 - 3:00 pm Tuesday Venue B303 Academic Building TA- Karamjeet Singh email- karamjeets@iiitd.ac.in Office hours- 1:30-2:30 pm , Thursdays Venue- B-514 R&D Block
TA-Anurag Goel Email: anuragg@iiitd.ac.in Office Hours: Friday, 1:30-2:30 pm Venue - A-614 R&D Block

Textbooks

Textbooks:
1.D. West:  Introduction to Graph Theory, Prentice Hall
 
 Reference Books:
1.Chartrand & Ping Zhang: Introduction to Graph Theory, Tata McGraw-Hill
2.Bela Bollobas: Modern Graph Theory, Springer-Verlag
3.Bondy & Murty: Graph Theory, Springer Verlag