  # 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 Sem 6 CBA-Graph Theory.pdf221.08 KB
branch:
CBA
Course:
2018
Stream:
B.Tech