Course Details
Subject {L-T-P / C} : CS4319 : Graph Theory and Network Algorithms { 3-0-0 / 3}
Subject Nature : Theory
Coordinator : Pankaj Kumar Sa
Syllabus
| Module 1 : |
Introduction: Graphs Degree Paths Cycles Connectivity Trees Forests Bipartite Graph Contraction Minors Euler Tours. Matching: Bipartite graph matching General graph matching Packing and covering. Connectivity: 2-Connected graphs and subgraphs Structure of 3-connected graphs Menger’s theorem Mader’s theorem Linking pairs of vertices. Planar Graphs: Topological prerequisites Plane graphs Kuratowski’s theorem Plane duality. Colour: Colouring maps and planar graphs, vertices, edges. Flows: Circulation Flows in networks Tutte’s flow conjectures. Extremal Graph Theory: Subgraphs Minors Hadwiger’s conjecture. Infinite Graphs. Ramsey Theory for Graphs. Hamiltonian Cycles. Random Graphs. |
Essential Reading
| 1 . |
Reinhard Diestel, Graph Theory, Springer-Verlag, Berlin Heidelberg |
| 2 . |
J. A. Bondy and U. S. R. Murty, Graph Theory, Springer-Verlag, London |
Supplementary Reading
| 1 . |
Douglas B. West, Introduction to Graph Theory, Pearson, India |
| 2 . |
Bela Bollobas, Graph Theory: An Introductory Course, Springer-Verlag, New York |