Course Objective
This is a post-graduate level course in graph theory. The objective of the course is to prepare the students for research in graph theory and related areas. Learning Outcomes: By the end of this course, students will have a rigorous foundation in the key areas of graph theory. They will be able to state, explain, prove, and apply many fundamental results in these areas. They will be able to analyse these proofs and apply these proof techniques to solve similar problems. They will also get confident to follow long and intricate graph theoretic arguments. They will also be familiar with some of the major open problems in the area.
Course Contents
Matching, Covering and Packing : Matching in bipartite graphs, Matching in general graphs, Tree packing and arboricity, Tree covering theorem, Path covers, Gallai-Milgram theorem, Dilworth’s theorem.
Connectivity : The structure of 2-Connected graphs, Block graph of a graph, The structure of 3- connected graphs, Menger’s theorem Linking pairs of vertices, k-linked graphs, relationship between connectivity and k-linkedness.
Planarity : Plane graphs, Euler’s formula, Planar graphs and Kuratowski’s theorem, Plane dual and Abstract dual.
Colouring : Colouring of planar maps, five colour theorem, Colouring vertices, Greedy vertex colouring, Brook’s thorem, Colouring edges, Konig’s theorem, Vizing’s theorem, List colouring, 5- choosability of planar graphs, Perfect graphs, Strong perfect graph theorem (statement only), Weak Perfect graph Theorem.
Hamilton cycles : Sufficient conditions, Hamilton cycles and degree sequences
A subset of topics from the following : Turan’s extermal graph theorem, Minors and Hadwiger’s conjecture, Tree-decompositions, Tree-width and Pathwidth, Forbidden minors, Random graphs and properties of almost all graphs, Ramsey theory for graphs.
Textbooks:
- Reinhard Diestel, Graph Theory, Fifth Edition, Springer-Verlag Berlin Heidelberg, 2017, ISBN:978-3-662-53621-6.
- Adrian Bondy and U. S. R. Murty, Graph Theory, Springer, 2008 edition, ISBN:978-1849966900.
References:
- Douglas B. West, Introduction to Graph Theory, Second Edition, Prentice Hall, 2001, ISBN: 978-8120321427.
Past Offerings
- Offered in Jan-May, 2018 by Deepak, Jasine
Course Metadata
| Item | Details |
|---|---|
| Course Title | Topics in Graph Theory |
| Course Code | CS6001 |
| Course Credits | 3-0-0-3 |
| Course Category | PME |
| Proposing Faculty | Jasine Babu & Deepak Rajendraprasad |
| Approved on | Senate 3 of IIT Palakkad |
| Course prerequisites | NIL |
| Course status | NEW |