Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Graph Theory WS 04-05
Theory of Combinatorial Algorithms Institute of Theoretical Computer Science Department of Computer Science ETH Zurich

Graph Theory (37-485) WS 04/05


Examination


Time & Place


Instructors

Lecturer: Tibor Szabó
IFW B48.1/ Tel: (01) 632-0858. e-mail: szabo@inf.ethz.ch

Assistant: Milos Stojakovic
IFW B43/ Tel: (01) 632-7239. e-mail: smilos@inf.ethz.ch

Abstract of the course

This course is an introduction to the theory of graphs intended for students in mathematics and computer science/engineering students with an interest in theory. We start from basic definitions and examples, but hope to move on quickly and cover a broad range of topics. Some applications and relations to Computer Science will also be discussed. Emphasis will be given to reading, understanding and developing proofs. There is no prerequisite, other than basic mathematics introduced in the Grundstudium. Possible topics include: degrees, paths, trees, cycles, Eulerian circuits, bipartite graphs, extremality, matchings, connectivity, network flows, vertex and edge colorings, Hamiltonian cycles and planarity.

Procedures, exam, exercises

Introduction to Graph Theory (Textbook) In lecture we will follow the textbook "Introduction to Graph Theory" by Doug West. In recitation we will sample from the great number of excellent exercises related to the topic of the current lecture. We do not require, but highly recommend that you try to solve all the homework exercises and if you do so, write them up. Writing up teaches you to precisely formulate your (maybe vague) ideas and communicate them such that others (in this case us) understand them. This ability is beneficial not just in mathematics but in (almost) any discipline. Whatever you write up we will read and comment on. Another reason to struggle with the homework problems is to prepare yourself for the final exam. Grading will solely be based on this two-hour, written exam, taking place in the Feb/March exam period following the course. Testat is given to those students who take this exam.

Language

English (written, spoken, whatever)

Course material


Lectures Transparencies
(1-in-1 version)
Transparencies
(4-in-1 version)
Problems Misc.

Lecture 1
October 20
(Basics I)
[PDF][PS] [PDF][PS] [PDF][PS] [PDF][PS]
<Welcome>
(Oct 20) (Oct 20) (Oct 20) (Oct 20)

Lecture 2
October 27
(Basics II)
[PDF][PS] [PDF][PS] [PDF][PS]
(Oct 27) (Oct 27) (Oct 27)

Lecture 3
November 3
(Extremal problems)
[PDF][PS] [PDF][PS] [PDF][PS]
(Nov 3) (Nov 3) (Nov 3)

Lecture 4
November 10
(Trees)
[PDF][PS] [PDF][PS] [PDF][PS]
(Nov 10) (Nov 10) (Nov 10)

Lecture 5
November 17
(Matchings I)
[PDF][PS] [PDF][PS] [PDF][PS]
(Nov 17) (Nov 17) (Nov 17)

Lecture 6
November 24
(Matchings II)
[PDF][PS] [PDF][PS] [PDF][PS]
(Nov 24) (Nov 24) (Nov 24)

Lecture 7
December 1
(Matchings III, Connectivity I)
[PDF][PS] [PDF][PS] [PDF][PS]
(Dec 1) (Dec 1) (Dec 1)

Lecture 8
December 8
(Network Flows, Connectivity II)
[PDF][PS] [PDF][PS] [PDF][PS]
(Dec 8, rev) (Dec 8, rev) (Dec 8)

Lecture 9
December 15
(Connectivity III, Coloring I)
[PDF][PS] [PDF][PS] [PDF][PS]
(revised Dec 22) (revised Dec 22) (Dec 15)

Lecture 10
December 22
(Coloring II)
[PDF][PS]
No new transparencies No new transparencies (Dec 22)

Lecture 11
January 12
(Edge-coloring)
[PDF][PS] [PDF][PS] [PDF][PS]
(Jan 12) (Jan 12) (Jan 12)

Lecture 12
January 19
(Turán-Type Problems)
[PDF][PS] [PDF][PS] [PDF][PS ]
(Jan 19) (Jan 19) (Jan 19)

Lecture 13
January 26
(Planar graphs I)
[PDF][PS] [PDF][PS] [PDF][PS ]
(Jan 26) (Jan 26) (Jan 26)

Lecture 14
February 2
(Planar graphs II)
No new transparencies No new transparencies [PDF][PS ]
(Feb 2)


Literature

Other (more advanced) texts:

Links



Acknowledgment. We are indebted to Yoshio Okamoto, who prepared detailed solutions to all hand-out exercises in the last year's course. Our solutions this year largely rely on that material.