Graph Theory
Code
9632
Academic unit
Faculdade de Ciências e Tecnologia
Department
Departamento de Matemática
Credits
6.0
Teacher in charge
Oleksiy Karlovych
Teaching language
Português
Objectives
1. Master a new mathematical language and its applications to the student’s research area.
2. Model a real world problem using concepts and results from Graph Theory.
3. Search solutions for real world problems using results and algorithms from Graph Theory.
Subject matter
The program of the discipline will be chosen among the following topics:
1. Graph representation, subgraphs, paths and cycles.
2. Connectivity: Bipartite graphs, Trees, Kruskal and Prim algorithms.
3. Eulerian and Hamiltonian graphs.
4. Stable sets and cliques.
5. Graph coloring and the 4 color theorem (without proof).
6. Planar Graphs.
7. Packing and covering.
8. Perfect graphs.
9. Matchings.
10. Graph decomposition.
11. Extremal Graph Theory.
12- Ramsey Theory.
13. The probabilistic method.
14. Random Graphs.
Bibliography
B. Bolobas, Extremal Graph Theory, Dover, 2004.
R. Diestel, Graph Theory, 4th edition, Springer, 2010.
F. Harary, Graph Theory, Addison-Wesley, 1972.
D.B. West, Introduction to Graph Theory, 2nd Edition, Prentice Hall, 2005.