Syllabus  |   Lectures  |   Downloads  |   FAQ  |   Ask a question  |
Course Co-ordinated by IIT Madras
 Coordinators IIT Madras

Download Syllabus in PDF format

Untitled Document
• Preliminaries: Graphs,  isomorphism,  subgraphs,  matrix representations,  degree,  operations on graphs, degree sequences
• Connected graphs and shortest paths: Walks, trails, paths, connected graphs, distance, cut-vertices, cut-edges, blocks, connectivity, weighted graphs,  shortest path algorithms
• Trees: Characterizations,  number of trees,  minimum spanning trees
• Special classes of graphs: Bipartite graphs,  line graphs,  chordal  graphs
• Eulerian graphs: Characterization,  Fleury’s algorithm,  chinese-postman-problem
• Hamilton graphs: Necessary conditions and sufficient conditions
• Independent sets, coverings, matchings: Basic equations,  matchings in bipartite graphs, perfect matchings,  greedy and approximation algorithms
• Vertex colorings: Chromatic number and cliques,  greedy coloring algorithm,  coloring of chordal graphs,  Brook’s theorem
• Edge colorings: Gupta-Vizing theorem,  Class-1 graphs and class-2 graphs,  equitable edge-coloring
• Planar graphs: Basic concepts,  Eulers formula,  polyhedrons and planar graphs,  charactrizations,  planarity testing, 5-color-theorem
• Directed graphs: Out-degree,  in-degree,  connectivity,  orientation,  Eulerian directed graphs,  Hamilton directed graphs,  tournaments
 Modules Contents  (optional topics are indicated in red) Number of lectures Number of lectures by skipping  optional topics 1 Preliminaries Graphs,  isomorphism,  subgraphs,  matrix representations,  degree,  operations on graphs, degree sequences 5-10 4 2 Connected graphs and shortest paths Walks, trails, paths, connected graphs, distance, cut-vertices, cut-edges, blocks, weighted graphs, connectivity, Dijkstra’s shortest path algorithm,  Floyd-Warshall  shortest path algorithm 4-8 4 3 Trees Characterizations,  number of trees,  minimum spanning trees 5-10 4 4 Special classes of graphs Bipartite graphs,  line graphs,  chordal  graphs 6-12 2 5 Eulerian graphs Characterization,  Fleury’s algorithm,  chinese-postman-problem 2-4 2 6 Hamilton graphs Necessary conditions and sufficient conditions 4-8 4 7 Independent sets, coverings and mathcings Basic equations,  matchings in bipartite graphs, perfect matchings,  greedy and approximation algorithms 8-16 6 8 Vertex-colorings Chromatic number and cliques,  greedy coloring algorithm,  coloring of chordal graphs,  Brook’s theorem 4-8 2 9 Edge-colorings Gupta-Vizing theorem,  Class-1 graphs and class-2 graphs,  equitable edge-coloring 8-16 6 10 Planar graphs Basic concepts,  Eulers formula,  polyhedrons and planar graphs,  charactrizations,  planarity testing, 5-color-theorem 10-20 3 11 Directed graphs Directed graph,   underlying graph, out-degree,  in-degree,  connectivity,  orientation,  Eulerian directed graphs,  Hamilton directed graphs,  tournaments 8-16 6

Text Books:
1. J.A. Bondy and U.S.R.Murty: Graph Theory and Applications ( Freely downloadable from Bondy's website; Google-Bondy)

2. D.B.West: Introduction to Graph Theory, Prentice-Hall of India/Pearson, 2009 ( latest impression)

Reference Books:
1. J.A.Bondy and U.S.R.Murty: Graph Theory, Springer, 2008.

2. R.Diestel: Graph Theory, Springer( low price edition) 2000.

1. F.Harary: Graph Theory, Narosa, (1988)

2. C. Berge: Graphs and Hypergraphs, North Holland/Elsevier, (1973)

 Important: Please enable javascript in your browser and download Adobe Flash player to view this site Site Maintained by Web Studio, IIT Madras. Contact Webmaster: nptel@iitm.ac.in