CS3203 Applied Graph Theory

Detailed syllabus:

1. Fundamental concepts: basic definitions, operations, properties, proof styles
2. Trees: properties, distances and centroids, spanning trees, enumeration
3. Matchings: bipartite graphs, general graphs, weighted matching
4. Connectivity: vertex and edge connectivity, cuts, blocks, k-connected graphs, network flows
5. Traversibility: Eulerian tours, Hamiltonian cycles); Coloring (vertex and edge coloring, chromatic number, chordal graphs
6. Planarity: duality, Euler's formula, characterization, 4-color theorem
7. Advanced topics: perfect graphs, matroids, Ramsay theory, extremal graphs, random graphs and Applications.

Text Books:
1. Douglas B. West, Introduction to Graph Theory, Prentice Hall of India.
2. Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science. Prentice-Hall.

Reference Books:
1. Frank Harary, Graph Theory, Narosa.
2. R. Ahuja, T. Magnanti, and J. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall.