CS60047: Advanced Graph Theory
| CS60047 | |||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Course name | Advanced Graph Theory | ||||||||||||||||||||||
| Offered by | Computer Science & Engineering | ||||||||||||||||||||||
| Credits | 4 | ||||||||||||||||||||||
| L-T-P | 3-1-0 | ||||||||||||||||||||||
| Previous Year Grade Distribution | |||||||||||||||||||||||
| |||||||||||||||||||||||
| Semester | Autumn | ||||||||||||||||||||||
Syllabus
Syllabus mentioned in ERP
Basic Concepts: Graphs and digraphs, incidence and adjacency matrices, isomorphism, the automorphism group; Trees: Equivalent definitions of trees and forests, Cayleys formula, the Matrix-Tree theorem, minimum spanning trees; Connectivity: Cut vertices, cut edges, bonds, the cycle space and the bond space, blocks, Menger s theorem; Paths and Cycles: Euler tours, Hamilton paths and cycles, theorems of Dirac, Ore, Bondy and Chvatal, girth, circumference, the Chinese Postman Problem, the Travelling Salesman problem, diameter and maximum degree, shortest paths; Matchings: Berges Theorem, perfect matchings, Halls theorem, Tuttes theorem, Konigs theorem, Petersens theorem, algorithms for matching and weighted matching (in both bipartitie and general graphs), factors of graphs (decompositions of the complete graph), Tuttes f-factor theorem; Extremal problems: Independent sets and covering numbers, Turans theorem, Ramsey theorems; Colorings: Brooks theorem, the greedy algorithm, the Welsh-Powell bound, critical graphs, chromatic polynomials, girth and chromatic number, Vizings theorem; Graphs on surfaces: Planar graphs, duality, Eulers formula, Kuratowskis theorem, toroidal graphs, 2-cell embeddings, graphs on other surfaces; Directed graphs: Tournaments, directed paths and cycles, connectivity and strongly connected digraphs, branchings; Networks and flows: Flow cuts, Max flow min cut theorems, perfect square; Selected topics: Dominating sets, the reconstruction problem, intersection graphs, perfect graphs, random graphs.
Concepts taught in class
Student Opinion
How to Crack the Paper
Classroom resources
Additional Resources
Time Table
| Day | 8:00-8:55 am | 9:00-9:55 am | 10:00-10:55 am | 11:00-11:55 am | 12:00-12:55 pm | 2:00-2:55 pm | 3:00-3:55 pm | 4:00-4:55 pm | 5:00-5:55 pm | |
|---|---|---|---|---|---|---|---|---|---|---|
| Monday | ||||||||||
| Tuesday | ||||||||||
| Wednesday | CSE-119 | |||||||||
| Thursday | CSE-119 | |||||||||
| Friday | CSE-119 | CSE-119 |