Core materials are available on the instructor's website:
http://homel.vsb.cz/~kov16/predmety_tg.php
Graph Theory
| Type of study | Follow-up Master |
|---|---|
| Language of instruction | Czech |
| Code | 470-4302/01 |
| Abbreviation | TG |
| Course title | Graph Theory |
| Credits | 6 |
| Coordinating department | Department of Applied Mathematics |
| Course coordinator | doc. Mgr. Petr Kovář, Ph.D. |
Subject syllabus
Lectures and discussions
- Graphs, simple graphs. Incidence matrix and adjacency matrix. Subgraphs. Degree of a vertex.
- Paths and cycles.
- Trees, bridges and cuts.
- Graph isomorphisms.
- Connectivity and blocks. Cut sets.
- Matching and covers in general and bipartite graphs. Perfect matchings.
- Edge colorings. Chromatic index, Vizing's Theorem.
- Vertex colorings, Chromatic number, Brook's Theorem.
- Planar graphs. Dual graphs, Euler's formula for connected planar graphs, Kuratowski's Theorem. Four Color Theorem.
- Non-planar graph, measures of non-planarity.
- Eulerian and Hamiltonian graphs.
- Oriented graphs. Oriented paths and cycles.
- Tournaments and graph models
- Graphs, simple graphs. Incidence matrix and adjacency matrix. Subgraphs. Degree of a vertex.
- Paths and cycles.
- Trees, bridges and cuts.
- Graph isomorphisms.
- Connectivity and blocks. Cut sets.
- Matching and covers in general and bipartite graphs. Perfect matchings.
- Edge colorings. Chromatic index, Vizing's Theorem.
- Vertex colorings, Chromatic number, Brook's Theorem.
- Planar graphs. Dual graphs, Euler's formula for connected planar graphs, Kuratowski's Theorem. Four Color Theorem.
- Non-planar graph, measures of non-planarity.
- Eulerian and Hamiltonian graphs.
- Oriented graphs. Oriented paths and cycles.
- Tournaments and graph models
E-learning
Literature
J. Matoušek, J. Nešetřil, Chapters in Discrete Mathematics, Karolinum Praha (2010).
Advised literature
D. B. West, Introduction to graph theory, Prentice-Hall, Upper Saddle River NJ, (2019), ISBN 9780131437371.