Graph Theory

Course Name: 

Graph Theory (CS315)


B.Tech (CSE)




Programme Specific Electives (PSE)

Credits (L-T-P): 



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.


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.

Contact us

Dr. Manu Basavaraju
Head of the Department
Department of CSE, NITK, Surathkal
P. O. Srinivasnagar, Mangalore - 575 025
Karnataka, India.
Hot line: +91-0824-2474053
Email: hodcse[AT]nitk[DOT]ac[DOT]in


Connect with us

We're on Social Networks. Follow us & get in touch.