Graph Theory, 7.5 Credits

Contents

The course treats more advanced topics in the theory of matchings and colourings of graphs,  and introduces several additional topics in advanced graph theory. In the theory of matchings, minimax theorems, and stable matchings in bipartites graphs are treated, along with Tutte's theorem on matchings and the flower algorithm for finding perfect matchings in general graphs. In graph colouring theory, the structure of graphs with a certain chromatic number is studied, and special classes where colouring problems can be solved efficiently are studied. Further topics in the course includes Ramsey theory, random graphs, and eigenvalues of graphs.

Expected learning outcomes

For a passing grade, the student must be able to

Knowledge and understanding

• give a detailed account for the theory matching and colouring
• define central families of graphs and account for their properties and mutual relations
• define Erdös-Renyi's random graph models, and derive basic results about their properties
• define eigenvalues for graphs, and prove their relation to expansion in graphs
• formulate and prove central theorems

Skills and abilities

• apply algorithms for finding matchings in bipartial and general graphs
• apply theorems for problem solving

Judgement and approach

Required Knowledge

The course requires 90 ECTS including a basic course in Graph Theory minimum 7,5 ECTS.

Form of instruction

The teaching on this course consists of lectures and exercise classes.

Examination modes

The course is examined through written exams. For the whole course, one of the following grades is assigned: Fail (U), Pass (G), Pass with distinction (VG). In order to pass the course, a student must have passed all parts of the assessment. 

Deviations from the syllabus examination form can be made for a student who has a decision on pedagogical support due to disability. Individual adaptation of the examination form shall be considered based on the student's needs. The examination form is adapted within the framework of the expected learning outcomes of the course syllabus. At the request of the student, the course coor-dinator, in consultation with the examiner, must promptly decide on the adapted examination form. The decision shall then be communicated to the stu-dent.

A student who has been awarded a passing grade for the course cannot be re-assessed for a higher grade. Students who do not pass a test or examination on the original date are given another date to retake the examination. A student who has sat two examinations for a course or a part of a course, without pass-ing either examination, has the right to have another examiner appointed, pro-vided there are no specific reasons for not doing so (Chapter 6, Section 22, HEO). The request for a new examiner is made to the Head of the Department of Mathematics and Mathematical Statistics. Examinations based on this course syllabus are guaranteed to be offered for two years after the date of the stu-dent's first registration for the course.

Credit transfer
All students have the right to have their previous education or equivalent, and  their working life experience evaluated for possible consideration in the corresponding ed-ucation at Umeå university. Application forms should be adressed to Student ser-vices/Degree evaluation office. More information regarding credit transfer can be found on the student web pages of Umeå university, http://www.student.umu.se, and in the Higher Education Ordinance (chapter 6). If denied, the application can be ap-pealed (as per the Higher Education Ordinance, chapter 12) to Överklagandenämnden för högskolan. This includes partially denied applications

Other regulations

In a degree, this course may not be included together with another course with a similar content. If unsure, students should ask the Director of Studies in Mathematics and Mathematical Statistics.