Advanced and algorithmic graph theory
3 lecture units and 1 practical unit per week
(MAT.464 / MAT.465)

E. Dragoti-Çela
Department of Discrete Mathematics

• Time and Place
  Lecture :
  Mondays, 08:15-10:00, SR AE06, Steyrergasse 30, ground floor
  Wednesdays, 14:15-15:45, SR AE06, Steyrergasse 30, ground floor (every second week)
  
  Practical:
  Wednesdays, 14:15-15:45, SR AE06, Steyrergasse 30, ground floor (every second week)

• Start: Monday, March 2, 2020, 08:15-10:00, SR AE06, Steyrergasse 30, ground floor
• Registration
via TUGonline until March 21, 2020
• Contents and prerequisites

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. Hence also a number of topics from the field of algorithmic graph theory and optimization problems in graphs will be considered.


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 26, 9:15-11:00, in SR AE02 (TUGonline-Name STEG006).


Another possibility will be around the beginning of the next winter term.
The registration for the exam has to be done via TUGonline. For the assessment will count the points collected during the most recent try.


The overall score is computed as follows


P= 3 * ((k)/(k_a)) + 12*(t) + 15 (p),


where


k     number of exercise examples prepared all along the course,


k_a   overall number of exercise examples which have been available during the course,


t     overall sum of points obtained by presenting exercise examples in the class (scaled between 0 and 1)


p     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.


• Some useful material (pdf)
  • General definitions and notations

  • General results on connectivity, 2-connectivity and 3-connectivity (Slides in latex)

  • Contents of the Lecture on March 16, 2020 Proofs, examples and illustrations related to 2-connectivity and 3-connectivity (handwritten)

  • Computing the connectivity-number, the edge connectivity number, checking for 2-connectivity and 3-connectivity

    (Slides in latex, part of the lecture on March 18)

  • Using DFS to check 2-connectivity and 3-connectivity

    (handwritten, part of the lecture on March 18)

  • Hamitonicity of graphs, sufficient conditions, necessary conditions (Slides in latex, part of the lecture on March 18)

  • Proofs and illustrations related to hamiltonicity

    (handwritten, part of the lecture on March 18)

  • Hamitonicity of graphs, sufficient conditions, longs cycles in graphs, degree sequences (Slides in latex, part of the lecture on March 23 and March 25)

  • Proofs, illustrations, examples related to hamiltonicity and long cycles

    (handwritten, part of the lecture on March 23)

  • Proof of Theorem 9, Chapter 3

    (handwritten, part of the lecture on March 25)

  • Chapter 4, Planar graphs 1 (Slides in latex, part of the lecture on March 25)

  • Chapter 4, some examples and the proofs of Prop. 1a and Prop 4 ,

    (handwritten, part of the lecture on March 25)

  • Chapter 4, Planar graphs 2 (Slides in latex, part of the lecture on March 30)

  • Chapter 4, examples on subdivisions and minors, proofs of the theorems of Kuratowski and Wagner ,

    (handwritten, part of the lecture on March 30)

  • Chapter 4, further examples, comments and proofs on forbidden minors, duals of planar graphs and recognition of planar graphs ,

    (handwritten, discussed in the video recorded on April 9)

  • Chapter 5, Coloring problems in graphs 1 (Slides in latex, part of the lecture on April 20)

  • Chapter 5, Coloring 1 examples, comments and proofs ,

    (handwritten, discussed in the video recorded on April 20)

  • Chapter 5, Coloring 1, proof of the theorem of Brooks,

    (handwritten, discussed in the video recorded on April 20)

  • Chapter 5, Coloring problems in graphs 2 (Slides in latex, part of the lecture on April 27)

  • Chapter 5, Coloring 2, proofs of König's Theorem and Vizing's Theorem

    (handwritten, discussed in the video recorded on April 27)

  • Chapter 5, Coloring 2, A missing Detail in the proof of Corollary 10

    (handwritten, discussed in the video recorded on April 27)

  • Chapter 5, Coloring problems in graphs 3 (Slides in latex, part of the lecture on April 29)

  • Chapter 5, Coloring 3, proofs of Corollary 12 of Vizing and Fournier

    (handwritten, discussed in the video recorded on April 29)

  • Chapter 5, Coloring 3, Proof of Theorem 14 of Galvin

    (handwritten, discussed in the video recorded on April 29)

  • Chapter 6, Perfect graphs 1: definitions, characterizations and other properties (Slides in latex, part of the lecture on May 4)

  • Chapter 6, Perfect graphs 1: proofs and examples

    (handwritten, discussed in the video recorded on May 4 and May 11)

  • Chapter 6, Chordal graphs: definitions, characterizations and recognition; other classes of perfect graphs

    (slides, discussed in the lecture on May 11, May 13, May 18)

  • Chapter 6, Chordal graphs 1: definitions and characterizations

    (handwritten, discussed in the video recorded on May 11 and May 13)

  • Chapter 6, Chordal graphs 2: properties and characterizations

    (handwritten, discussed in the video recorded on May 13)

  • Chapter 6, Chordal graphs 3: characterizations and recognition; other classes of perfect graphs

    (handwritten, discussed in the video recorded on May 18)

  • Chapter 7, Random graphs 1: definition of the probability space, example of computing (bounds on) probabilities of simple events, Ramsey numbers, the probabilistic method

    (handwritten, the first part, until Theorem 7.4, was discussed and annotated during the lecture on May 25, the rest during the lecture on May 27)

  • Chapter 7, Random graphs 2: the probabilistic method continued, almost sure and almost inexistent properties

    (handwritten, discussed and annotated during the lecture on May 27 and on June 8)

  • Chapter 7, Random graphs 1 (slides)

    (latex, summary of definitions, theorems, lemmas, ... discussed during the lectures on May 25 and 27)

  • Chapter 7, Random graphs 3

    (handwritten, almost sure properties for fixed edge existence probabilities, threshold of properties, discussed during the lecture on June 8 and June 10)

  • Chapter 7, Random graphs 3 (continued)

    (handwritten, threshold of properties, discussed during the lecture on June 10)

  • Chapter 7, Random graphs 2 (slides)

    (latex, properties of almost all graphs, threshold of properties, discussed during the lecture on May 27, June 8 and June 10)

  • Chapter 8, Well-quasi-orders (WQO) and tree-decompositions 1,

    (handwritten, a dynamic programming scheme for the maximum weighted stable set problem on trees, definition of WQO, , discussed during the lecture on June 15)

  • Chapter 8, Well-quasi-orders (WQO) and tree-decompositions 2

    (handwritten, WQO, (topological) minors relations (in trees) and tree-decompositions, discussed during the lecture on June 15 and June 22)

  • Chapter 8, Well-quasi-orders (WQO) and tree-decompositions 3

    (handwritten, tree-decompositions and their properties, the treewidth of a graph, discussed during the lecture on June 22)

  • Chapter 8, Well-quasi-orders (WQO) and tree-decompositions 4

    (handwritten, tree-decompositions and their properties, solving the maximum weight independent set problem efficientlyl on graphs with bounded tree-width, discussed during the lecture on June 24)

  • Chapter 8, Well-quasi-orders (WQO) and tree-decompositions

    (sliedes in latex, summary of definitions, notations and most important results of Chpater 8 excludign proofs)

  • The most recent video
    • Chapter 8: Well-quasi-orderings and tree-decompositions 3, lecture on June 24

• Work sheets (pdf)
  (The current work sheet will be published here at least one week before the next practical unit.)
  • First worksheet (to be discussed on Wednesday, March 11)

  • Second worksheet (solutions are to be submitted until Monday, March 30)

  • Third worksheet (solutions are to be submitted until Wednesday, May 6, 8 a.m., they will be discussed in the practical unit on May 6, 2 p.m.)

  • fourth worksheet (solutions are to be submitted until Wednesday, May 20, 9 a.m., they will be discussed in the practical unit on May 20, 2 p.m.)

  • fifth worksheet (solutions are to be submitted until Wednesday, June 3, 9 a.m., they will be discussed in the practical unit on June 3, 2 p.m.)

  • sixth worksheet (solutions are to be submitted until Wednesday, June 27, 9 a.m., they will be discussed in the practical unit on June 17, 2 p.m.)

Back to my homepage

Last update: July 2020