### MA6230 GRAPH THEORY

#### Course Details

Basics: subgraphs, isomorphism, automorphism group, matrices associated with graphs, degrees, walks, connected graphs, shortest path algorithms.

Connectivity: Connectivity and Mengers theorem; Structure of 2-connected and 3-connected graphs, Maders theorem.

Matchings: Berge's theorem, Hall's theorem, Tutte's perfect matching theorem, k-matchings (reduction to perfect matching problem), job-assignment-problem.

Ramsey Theory: Pigeonhole Principle, Ramsey Theorem, Ramsey Numbers.

Eulerian and Hamiltonian graphs: characterization of Euler graphs, necessary/ sufficient conditions for the existence of Hamilton cycles, Fleury's algorithm for eulerian trails, Chinese-postman-problem (complete algorithmic solution), approximate solutions of traveling salesman problem.

Planar Graphs: Euler's formula, Dual graphs, Characerization of planar graphs, planarity testing.

Coloring: Brooks' Theorem, Graphs with large chromatic number, Turan's theorem.

#### Course References:

Books:

1. D.B. West, Introduction to graph theory, PHI Learning, New Delhi, 2004.

References:

1. J.A. Bondy and U.S.R. Murty, Graph Theory and Applications, GTM Vol. No. 244, Springer 2008.

2. R. Diestel, Graph Theory, Springer, 2006.