NMAK15015U  Graph Coloring

Volume 2015/2016
Education

MSc programme in Mathematics

Content

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

Knowledge
Basic graph theory directed at coloring problems.

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


Competence
Bound chromatic numbers by a variety of techniques.

 

To be announced.

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

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