Course Objective
The objective of this course is to introduce the students to various techniques in graph theory and combinatorics.
Course Contents
Matching, Hall's Theorem, Kőnig's Theorem, Connectivity, Coloring, Planar Graphs, Eulerian Graphs, Hamiltonian cycles, Dirac's Theorem, Ore’s Theorem. (12 lectures)
Introduction to Ramsey Theory and Extremal Graph Theory. (8 lectures)
Ordinary, Exponential and other special Generating Functions, Formal Power Series. (10 lectures)
Linear Algebraic Arguments like Dimensionality, Orthogonality and Rank arguments. Introduction to Spectral Graph Theory. (12 lectures)
Learning Outcomes:
By the end of this course, students will be able to state, explain, prove, and apply fundamental results in graph theory and combinatorics. They will be able to analyse these proofs and apply these proof techniques to solve similar problems.
Text Books:
- Reinhard Diestel, Graph Theory, Fifth Edition, Springer-Verlag Berlin Heidelberg, 2017, ISBN: 978-3-662-53621-6.
- F. R. K Chung, Spectral Graph Theory, ISBN: 978-0-8218-0315-8.
- László Babai and Péter Frankl, Linear Algebra Methods in Combinatorics With Applications to Geometry and Computer Science, Preliminary Version 2, 1992.
References:
- Adrian Bondy and U. S. R. Murty, Graph Theory, Springer, 2008 Edition, ISBN: 978- 1849966900.
- Chris Godsil and Gordon Royle, Algebraic Graph Theory, Springer, 2001, ISBN: 978-0- 387-95220-8.
- Norman Biggs, Algebraic Graph Theory, Cambridge University Press, 1994. ISBN-13: 978- 0521458979.
- D.B West, Introduction to Graph Theory, Prentice Hall, 1996. ISBN: 9780132278287.
Past Offerings
- Offered in Jan-May, 2024 by Srimanta Bhattacharya
- Offered in Jan-May, 2023 by Srimanta Bhattacharya
- Offered in Jan-May, 2022 by Krithika Ramaswamy
- Offered in Jan-May, 2021 by Jasine
Course Metadata
| Item | Details |
|---|---|
| Course Title | Graph Theory and Combinatorics |
| Course Code | CS5010 |
| Course Credits | 3-0-0-3 |
| Course Category | PMT |
| Proposing Faculty | Deepak Rajendraprasad |
| Approved on | Senate 11 of IIT Palakkad |
| Course status | NEW |