Bookmark and Share

Graph Theory II


Technical University of Denmark


General course objectives:
The course includes a number of classical results such as the theorems of Tutte, Ramsey, Turan, Kuratowski, Brooks, Dirac, Smith, and Vizing, respectively, and also the Jordan Curve Theorem. The course also includes more recent themes, for example list-colorings.

Learning objectives:
A student who has met the objectives of the course will be able to:
  • Apply generating functions
  • Apply counting technique illustrated by Ramsey's theorem
  • Apply the foundation for planar graphs: The Jordan Curve Theorem
  • Apply the Kuratowski Planarity Criterion
  • Understand and apply the classical theorems by Turan, Brooks, Dirac, Smith and Vizing
  • Apply algebraic methods illustrated by the chromatic polynomial
  • Apply the list color methods
  • Understand the implications of large minimum valency

Contents:
1.Generating functions, the Catalan numbers. 2.Tutte’s 1-factor theorem. Petersen’s theorem. 3.The theorems of Ramsey og Turan. 4.The Jordan Curve Theorem. 5.Kuratowski’s theorem on planar graphs. 6.Hamilton cycles. Dirac’s theorem and the Grinberg criterion. 7.The number of hamilton cycles (Smith’s theorem) , chromatic number and maximum degree (Brooks’ theorem). 8.Vizing’s theorem on chromatic index. 9.Chromatic polynomial. 10.List-coloring. 5-coloring of planar graphs. 11.Graphs of large chromatic number and large girth. 12.Mader’s results on configurations in graphs of large minimum degree.

Back

Lecturer
Carsten
Place/Venue
Anker Engelunds Vej 1
City
Kgs. Lyngby
Country
Denmark
ECTS
5 points
Link
http://www.kurser.dtu.dk/01527.aspx?menulangu...
Language
English
Block-scheduling
No
Cost
Not available