Graph Labelings, Colorings and their Applications (16h)

Detailed program  

Prof.ssa Anita Pasotti
Dr. Tommaso Traetta
Università di Brescia

This course focuses on two fundamental subjects in graph theory: labelings and colorings. We will see how these topics originated through their practical applications, the main known results and some of the many problems still open.
No previous knowledge of graph theory is required.


Monday, 1 March 2021, 9.30-11.30
Preliminary concepts. Vertex labelings. Ringel-Kotzig conjecture.

Tuesday, 2 March 2021, 9.30-11.30
Graceful tree conjecture. Graceful graphs.

Thursday, 4 March 2021, 9.30-11.30
Generalizations and applications of graceful labelings. Vertex-colorings.

Friday, 5 March 2021, 9.30-11.30
Sequential vertex-coloring algorithm. Five-color theorem and four-color theorem. Applications.

Monday, 8 March 2021, 9.30-11.30
Edge-colorings. Sequential edge-coloring algorithm.

Tuesday, 9 March 2021, 9.30-11.30
Bipartite graphs and Koenig’s theorem. Connections with graph decompositions,
factorizations and applications.

Thursday, 11 March 2021, 9.30-11.30
1-factorizations and applications to tournaments. Perfect 1-factorization conjecture.

Friday, 12 March 2021, 9.30-11.30
2-factorizations, the Oberwolfach problem and its generalizations. Open problems.


If you are interested to attend this course, you are required to fill out this form.


The course will take place through synchronous lessons on Microsoft Teams. Students interested are requested to contact:

Prof.ssa Anita PASOTTI
Dept. of Civil, Environmental, Architectural Engineering and Mathematics (DICATAM)