Course Instructor: Dalu Jacob co-taught with Prof. Ashutosh Rai,
Office: 527 B, Academic complex West (99B), dalujacob@math.iitd.ac.in
Time and Venue: Tue, Fri 3:30-4:50 pm , LH 318
Teaching Assistants:
Sonam Gariya, maz238700@iitd.ac.in@maths.iitd.ac.in
Syllabus:
We will roughly cover the following topics: Introduction to Graphs: Definition and basic concepts; Trees: characterizations, counting of minimum spanning tree; Paths and Distance in Graphs: Basic Definitions, center and median of a graph, activity digraph and critical path; Eulerian Graphs: Definition and Characterization; Hamiltonian Graphs: Necessary and sufficient conditions, Planar Graphs: properties, dual, genus of a graph; Graph Coloring: vertex coloring, chromatic polynomials, edge coloring, planar graph coloring; Matching and Factorizations: maximum matching in bipartite graphs, maximum matching in general graphs, Hall’s marriage theorem, factorization; Networks: The Max-flow min-cut theorem, connectivity and edge connectivity, Menger’s theorem; Graph and Matrices.
Evaluation Plan
2 Quizzes (15 marks each) : 30 marks
Minor: 30 marks
Major: 35 marks
Attendance: For at least 85 percent attendance you get 5 marks, for at least 80 but less than 85, you get 2 marks, and no attendance points for less than 80 percent attendance. Attendance will be done through rollcall.
References
Primary reference: Introduction To Graph Theory, D. B. West [link]
Additional references:
Graph theory, Reinhard Diestel [link]
Graph theory with Applications, J. A. Bondy and U. S. R. Murty [link]
Topics covered
Lecture 1-13: Refer to this.
Lecture-14: 2-connected graphs: blocks, block decomposition, Whitney's theorem for 2-connectedness, Ear Decomposition (Reference: Chapter 4, Section 4.2, D. B. West).
Lecture-15: k-connected graphs, Menger's theorem, line graphs and k-edge connectivity (Reference: Chapter 4, Section 4.2, D. B. West).
Lecture-16: Graph coloring: Some upper and lower bounds, Greedy coloring, Coloring interval graphs (Reference: Chapter 5, Section 5.1, D. B. West).
Lecture-17: Brook's theorem (Reference: Chapter 5, Section 5.1, D. B. West).
Lecture-18: Mycielski Construction, Gallai-Roy-Vitaver theorem (Reference: Chapter 5, Section 5.2 D. B. West).
Lecture-19: Extremal problems and Turan's theorem, Color critical graphs and some of their properties (Reference: Chapter 5, Section 5.2, D. B. West).
Lecture-20: Connectivity of color critical graphs, counting proper colorings, chromatic polynomial, recursive formulation (Reference: Chapter 5, Section 5.3, D. B. West).
Lecture-21 Chordal graphs: Perfect elimination ordering characterization, chromatic polynomial using P.E.O. (Reference: Chapter 5, Section 5.3, D. B. West).
Lecture-22: Edge coloring: in bipartite graphs, Vizing's theorem (Reference: Chapter 7, Section 7.1, D. B. West).
Lecture-23: Introduction to Planar graphs: Some basic defnitions, dual graphs (Reference: Chapter 6, Section 6.1, D. B. West).
Lecture-24: Euler's formula and its applications, Preparation for Kuratowski's theorem (Reference: Chapter 6, Section 6.1, 6.2 D. B. West).