
Time and Place
Lecture
:
Mondays, 08:1510:00, SR AE06, Steyrergasse 30, ground floor
Wednesdays, 10:1512:00, SR Analysis und Zahlentheorie, Kopernikusgasse 24, second floor (every second week)
Practical:
Wednesdays, 10:1512:00, SR Analysis und Zahlentheorie, Kopernikusgasse 24, second floor (every second week)

Start: Monday, March 4, 2024, 08:1510:00, SR AE06, Steyrergasse 30, ground floor

Registration
via TUGonline until March 17, 2024

Contents
This course deals with concepts from graph theory such as connectivity, trees and decompositions,
Hamiltonian cycles, planar graphs, graph coloring, perfect graphs, covering problems and random graphs.
Most of the topics will be discussed both from a theoretical and from an algorithmical point of view.
Chapters:
 Connectivity, trees and decompositions
 Hamiltonian cycles
 Planar graphs and plane duality
 Colouring problems
 Perfect graphs
 Covering problems
 Random graphs and randomized algorithms

Literature
The main sources of literature

Bella Bollobas, Modern Graph Theory (Graduate Texts in Mathematics), corrected and extended edition, Springer, 2013.

G. Chartrand, L. Lesniak, P. Zhang, Graphs & Digraphs (Textbooks in Mathematics), Taylor & Francis Inc, 6th revised edition, 2015.

R. Diestel, Graph Theory (Graduate Texts in Mathematics), fourth edition, (second, corrected printing) Springer, 2012

M.Ch.Golumbic, Algorithmic graph theory and perfect graphs, second edition, Elsevier Ltd, 2004

Assessment
The practical assessment will be permanent and based on a score of points collected as follows
 by solving exercise examples independently; at most 3 points;
At the beginning of every practical class the participants have to declare
which exercise examples they have solved and prepared for presentation.
At the end of the course they will be credited with the percentage of the exercise examples they have declared to have solved during the course multiplied by three

by presenting the solution of exercise examples in the class;
The presentatation of an exercise example in the class will be credited with at most 4 points corresponding to the correctness and completeness of the solution as well as the quality of the presentation.

by participating at a written exam at the end of the course; at most 15 points. For a positive grade at the practical you should reach a minimum of 6 points (out of 15) at the written exam.
The written exam: The first possibility to take the writen exam will be at the end of the course, most probably on June 28, 15:0017:00, in SR AE06 (TUGonlineName STEG050).
Another possibility will be around the beginning of the next winter term.
The registration for the exam has to be done via TUGonline.
The points collected during the most recent try will count for the assessment .
The overall score is computed as follows
P= 3 * ((k)/(k_a)) + 12*(t) + 15 (p),
where
k is the number of exercise examples prepared all along the course,
k_a is the overall number of exercise examples which have been available during the course,
t is the overall sum of points obtained by presenting exercise examples in the class (scaled between 0 and 1)
p is the score of the written exam (scaled between 0 und 1),
Grade obtained for the practical according to the overall score:
5 0 <= P < 15
4 15 <= P <= 18
3 18 < P <= 22
2 22 < P <=26
1 26< P
The lecture will be assessed by an oral examination.
The dates for the oral exams will be specified in agreements with the students.

Learning materials
(pdf)
 General definitions and notations
 Recall some very basic results on maximum flows and minimum cuts in networks (slides)
For proofs and further results in these topics I refer to Chapter 8 in
Bernhard Korte and Jens Vygen,
Combinatorial Optimization : Theory and algorithms,
Springer, 2012,
eltronically available in TUG campus.
 General results on connectivity, 2connectivity and 3connectivity
 Computing the connectivitynumber, the edge connectivity number, checking for 2connectivity and 3connectivity
 Hamitonicity of graphs, sufficient conditions, necessary conditions
 Hamitonicity of graphs, sufficient conditions, longs cycles in graphs, degree sequences

Worksheets (pdf)
(The current work sheet will be published here at least one week before the next practical unit.)
cela@opt.math.tugraz.ac.at.
Back
to my homepage
Last update:
March 2024