Course Description

MATH 8001. Graph Theory I

Course Code MATE 8001
Course Title Graph Theory I
Credits 3
Hours 3 per week
Prerequisites MATH 5CCC
Description Review of elementary graph theory. Trees. Matrix-tree theorem. Enumerating spanning trees of a graph. Graph decompositions. Connectivity and k-connectivity of graphs. Disjoint paths and connectivity of graphs. Menger’s and Whitney’s theorems. Graph assembling and disassembling of 3-connected and quasi 4-connected graphs. Various Euler problems. Hamiltonian cycles. The k-closure of a graph. Bondy-Chvátal’s theorem. Long cycles in a graph. Dirac’s theorem. Factors. Maximum and perfect matchings. Tutte’s and Edmonds-Gallai’s theorems. Berge-Tutte duality theorem. Perfect graphs. Lovász’ theorem. Edge colorings. Vizing’s theorem. Independent sets and cliques. Vertex colorings. Brook’s theorem. Embeddings of graphs in the plane. Kuratowski’s, Whitney’s, MacLane’s, and Kelmans’ planarity criteria. Five-colour and four-colour theorems on planar graphs. On the hamiltonicity of planar graphs.
Additional Information