Login
Course Information
Identification

CS 408: Graph Theory
 
Description

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.
 
References

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
 
Prerequisites

N/A
 
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

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback