Graph Theory
Course Name:
Graph Theory (CS315)
Programme:
B.Tech (CSE)
Semester:
Fifth
Category:
Programme Specific Electives (PSE)
Credits (L-T-P):
04(3-1-0)
Content:
Graphs, Preliminaries on Graphs, Matchings in Bipartite graphs- Konig ’s theorem, Hall’s theorem. Matchings in
general graphs- Tutte’s theorem, 2-connected graphs, Ear-decomposition, Menger’s theorem, Dirac’s extensions for
Menger ’s theorem. Edge connectivity, Vertex coloring- Greedy coloring, Degeneracy of graphs, Coloring of planar
graphs, Brook’s theorem, Edge coloring- Konig’s theorem, Vizing’s theorem, Perfect graphs. Hamiltonian graphs,
Ramsey theoretic problems, Structure of minimum cuts in a graphs, Discharging method, Network flows.
References:
R. Diestel, Graph Theory, Second edition, Springer, 2000.
D. West, Introduction to Graph Theory, Second Edition, PHI, 2003.
J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North Holland, 1976.
A. Schrijver, A course in Combinatorial Optimization, Cambridge university press, 2000.