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
1

Basics

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

2

Structure and Symmetry

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

3

Trees and connectivity

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

4

Eulerian and Hamiltonian graphs

Characterization of Eulerian graphs - Sufficient conditions for Hamiltonian graphs

5

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

6

Marching, factors, decomposition and domination

7

Extremal Graph theory

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

Text Books: 
Name : 
Graph Theory
Author: 
by J. A. Bondy
U. S. R. Murthy
Publication: 
Springer Verlag
Name : 
Introduction to Graph Theory
Author: 
by D. B. West
PHI, 2004
Reference Books: 
Name: 
Graph Theory
Author: 
by R. Diestel
Publication: 
Springer Verlag
Syllabus PDF: 
AttachmentSize
PDF icon Sem 6 CBA-Graph Theory.pdf221.08 KB
branch: 
CBA
Course: 
2018
Stream: 
B.Tech