We give a systematic
introduction to some core areas of combinatorics and graph theory,
with special emphasis on links between seemingly unrelated areas
and on applications to problems in other parts of mathematics
and computer science. Some basic knowledge of combinatorics,
linear algebra, and calculus are required.
We cover the following
- Chromatic number vs. clique number, perfect graphs
- Coloring algorithms, greedy and probabilistic
- Graph minors, Hadwigers's conjecture, Hajós theorem
- Large topological minors in dense graphs
- Menger's theorem, Konig-Hall theorems, connectivity
- Lipton-Tarjan separator theorem, divide-and-conquer
- Applications of linear algebra
- Combinatorial designs
R. Diestel: Graph Theory, Springer, 1997, 2000.
B. Bollobás: Modern Graph Theory, Springer, 1998.
S. Jukna: Extremal Combinatorics, Springer, 2001.