Apero

You are invited to join the Apero after the whole course. It will take place from 16:00 on February 4, Wednesday at the round area in front of IFW B48.2.

Examination

• Date: March 2 (Tuesday), 2004
• Time: 9:00 - 11:00 AM
• Place: HG F19 (Room F19 of the Main Building of ETH)
• Detail: [PDF][PS]
• Administration: Mathematics students and graduate students, please send an email to us to tell whether you are going to take the exam or not.

Time & Place

• Lectures: Wed 10-12 @ IFW B42.
  
• Exercises: Wed 15-16 @ IFW B42.

Instructors

Lecturer: Tibor Szabó

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

Assistant: Yoshio Okamoto

IFW B48.2/ Tel: (01) 632-7148. e-mail: okamotoy@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

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.

Language

English (written, spoken, whatever)

Course materials

Lectures	Transparencies (1-in-1 version)	Transparencies (4-in-1 version)	Problems	Misc.
Lecture 1 October 22 (Basics I)	[PDF][PS]	[PDF][PS]	[PDF][PS]	[PDF][PS] <Welcome>
	(Oct 23, rev)	(Oct 23, rev)	(Oct 22)	(Oct 23, rev)
Lecture 2 October 29 (Basics II)	[PDF][PS]	[PDF][PS]	[PDF][PS]
	(Oct 28)	(Oct 28)	(Oct 28)
Lecture 3 November 5 (Extremal Problems)	[PDF][PS]	[PDF][PS]	[PDF][PS]
	(Nov 5)	(Nov 5)	(Nov 5)
Lecture 4 November 12 (Trees)	[PDF][PS]	[PDF][PS]	[PDF][PS]
	(Nov 12)	(Nov 12)	(Nov 19, rev)
Lecture 5 November 19 (Matchings I)	[PDF][PS]	[PDF][PS]	[PDF][PS]
	(Nov 19)	(Nov 19)	(Nov 19)
Lecture 6 November 26 (Matchings II)	[PDF][PS]	[PDF][PS]	[PDF][PS]
	(Dec 3, rev)	(Dec 3, rev)	(Dec 1, rev)
Lecture 7 December 3 (Matchings III & Connectivity I)	[PDF][PS]	[PDF][PS]	[PDF][PS]
	(Dec 3, rev)	(Dec 3, rev)	(Dec 3, rev)
Lecture 8 December 10 (Network Flows & Connectivity II)	[PDF][PS]	[PDF][PS]	[PDF][PS]
	(Dec 10)	(Dec 10)	(Dec 10)
Lecture 9 December 17 (Connectivity III & Coloring I)	[PDF][PS]	[PDF][PS]	[PDF][PS]
	(Jan 6, rev)	(Jan 6, rev)	(Dec 17)
Lecture 10 January 7 (Coloring II)	No new slides	No new slides	[PDF][PS]
			(Jan 6)
Lecture 11 January 14 (Turán-Type Problems)	[PDF][PS]	[PDF][PS]	[PDF][PS]
	(Jan 13)	(Jan 13)	(Jan 16, rev)
Lecture 12 January 21 (Edge-coloring)	[PDF][PS]	[PDF][PS]	[PDF][PS]
	(Jan 20)	(Jan 20)	(Jan 20)
Lecture 13 January 28 (Planar graphs I)	[PDF][PS]	[PDF][PS]	[PDF][PS]	[PDF][PS] <Exam Info>
	(Jan 27)	(Jan 27)	(Jan 27)	(Jan 27)
Lecture 14 February 4 (Planar graphs II)	No new slides	No new slides	[PDF][PS]
			(Feb 3)
Lectures	Transparencies (1-in-1 version)	Transparencies (4-in-1 version)	Problems	Misc.

Literature

• Douglas B. West, Introduction to Graph Theory (2nd edition) , Prentice Hall, 2001.
• J. A. Bondy and U. S. R. Murty, Graph Theory with Applications , 1976.

• B. Bollobás, Modern Graph Theory, Springer, 1998.
• R. Diestel, Graph Theory , Springer, 2000. (German Edition is also available).

Links

• Robin Thomas's page on the new proof of the Four Color Theorem .
• Vasek Chvátal's page on the Strong Perfect Graph Theorem.
• Bjarne Toft's page on Graph Coloring Problems.
• Stephen Locke's page on Unsolved Problems.
• Douglas West's page on Open Problems.
• Dan Archdeacon's page on Problems in Topological Graph Theory.

Last modified:Sun Mar 21 14:53:01 2004 by Yoshio Okamoto.