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