Syllabus  |   Lectures  |   Downloads  |   FAQ  |   Ask a question  |  
Course Co-ordinated by IIT Madras
Coordinators
 
Prof. S.A. Choudum
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