2CSE60E6: Graph Theory

Learning Outcomes: 
After learning the course the students should be able to
Solve problems using basic graph theory
Identify induced subgraphs, cliques, matchings, covers in graphs
Determine whether graphs are Hamiltonian and/or Eulerian
Solve problems involving vertex and edge connectivity, planarity and crossing numbers
Solve problems involving vertex and edge coloring
Model real world problems using graph theory
Syllabus: 
Unit NoTopics
Basics

Graphs, degree sequences, distance in graphs, complete, regular and bipartite graphs, basic properties

Structure and Symmetry

Cut vertices, bridges and blocks, automorphism groups, reconstruction problem

Trees and connectivity

Properties of trees, Arboricity, vertex and edge connectivity, Mengers  theorem

Eulerian and Hamiltonian graphs

Characterization of Eulerian graphs - Sufficient conditions for Hamiltonian graphs

Colouring and planar graphs

vertex and edge colouring, perfect graphs, planar graphs, Euler's theorem, Kuratowski's theorem, Colouring of planar graphs, Crossing number and thickness

Matching, factors, decomposition and domination

External Graph theory

Turan's theorem, Ramsay's theorem, Szemeredi's regularity lemma applications

Text Books: 
Name : 
Graph Theory
Author: 
by J. A. Bondy and U. S. R. Murthy
Publication: 
Springer Verlag (2008.)
Name : 
2. Introduction to Graph Theory
Author: 
by D. B. West
Publication: 
PHI, 2004.
Reference Books: 
Name: 
Graph Theory
Author: 
by R. Diestel
Publication: 
Springer Verlag
Syllabus PDF: 
AttachmentSize
PDF icon 6th Graph Theory.pdf180.1 KB
branch: 
CBA
Course: 
2014
2016
Stream: 
B.Tech