NMAK15015U  Graph Coloring

Volume 2015/2016

MSc programme in Mathematics


Coloring problems associated to graphs. Graphs and their chromatic numbers and chromatic polynomials. The Potts model, chromatic numbers of R^n, chromatic numbers of simplicial complexes, topological bounds on the chromatic number á la Lovasz etc.

Learning Outcome

Basic graph theory directed at coloring problems.

Use of chromatic polynomials. Experimentation with given classes of graphs.

Bound chromatic numbers by a variety of techniques.


To be announced.

4 hours lectures and 3 hours excercises each week for 9 weeks.
7,5 ECTS
Type of assessment
Continuous assessment
3 mandatory homework assignments.
All aids allowed
Marking scale
passed/not passed
Censorship form
No external censorship
One internal examiner

Oral exam, 30 minutes without preparation time. Several internal examiners

Criteria for exam assesment

The student must in a satisfactory way demonstrate that he/she has mastered the learning outcome of the course.

  • Category
  • Hours
  • Lectures
  • 36
  • Exercises
  • 27
  • Project work
  • 45
  • Preparation
  • 98
  • Total
  • 206