Course Details
Subject {L-T-P / C} : CS4319 : Graph Theory and Network Algorithms { 3-0-0 / 3}
Subject Nature : Theory
Coordinator : Prof. Pankaj Kumar Sa
Syllabus
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.
Course Objectives
- -
Course Outcomes
-
Essential Reading
- Reinhard Diestel, Graph Theory, Springer-Verlag, Berlin Heidelberg
- J. A. Bondy and U. S. R. Murty, Graph Theory, Springer-Verlag, London
Supplementary Reading
- Douglas B. West, Introduction to Graph Theory, Pearson, India
- Bela Bollobas, Graph Theory: An Introductory Course, Springer-Verlag, New York