Course Information

CS 408: Graph Theory

Matchings: Hall’s matching condition, Tutte’s 1-factor theorem, Petersen’s theorem, f-Factors of graphs, Weighted bipartite matching algorithm, Stable matching algorithm, Edmond’s Blossom algorithm. Connectivity: Vertex and edge connectivity, Ear decomposition, Menger’s theorem, Mader’s disjoint paths theorem. Coloring of Graphs: Vertex coloring, Brook’s theorem, Edge coloring, Vizing’s theorem, List coloring. Planar Graphs: Euler’s formula, Characterization of planar graphs, Coloring of planar Graphs, Dual graphs, Crossing number Extremal Graph Theory: Turan’s theorem, Graph Ramsey theory, Dirac’s theorem. Selected Advanced Concepts: Perfect graphs, Partitioning graphs into paths and cycles, Random graphs.

Douglas B. West, Introduction to Graph Theory, Second Edition, Pearson Education Asia, 2002.

2. Bela Bollobas, Modern Graph Theory, Springer-Verlag New York, 1998.

3. Reinhard Diestel, Graph Theory, Third Edition, Springer-Verlag Heidelberg, 2005.

4. J.A. Bondy and U.S.R Murty, Graph Theory, Springer, 2008.
Home Page

Not Available

Other Details

Duration : Full Semester Total Credit : 0
Type : Theory
Current Semester (Autumn 2017-18)

Status : Not Offered Instructor : ---
Next Semester (Spring 2017-18)

Status : Offered Instructor : Prof. Ajit A. Diwan

Last Modified Date: 09-May-2016


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback