Duration: 1. 7. 2022 – 30. 6. 2024

Coordinator: Graph Theory Laboratory

Project leader: Assoc. Prof. Borut Lužar, Ph.D.

Type of the project: Bilateral project

Short description of the project:

Graph theory is a young branch of mathematics. Its foundations were laid by Euler in 18thcentury by solving the Bridges of Königsberg Problem. The Four Color Problem, dated around 1852, is the second widely recognized problem in the field. It took over a hundred years to answer it in affirmative. The conjecture attracted scientists from all fields of mathematics and contributed to development of new methods not only in discrete mathematics, but also in algebra, topology, computer science and others. Chromatic graph theory is at present one of the most prominent branches of graph theory, divided in a number of research directions or problem types.

The fundamental problem in chromatic graph theory is to specify the least number of colors with which the vertices of a graph can be colored in such a way that the neighboring vertices receive distinct colors. The problem is in general, as many of its variations, NP-hard. Additional structural properties, such as embedding in a surface, bounded maximum degree, or forbidden substructures, can be exploited to obtain non-trivial bounds and tractability.  Numerous variants of graph coloring, motivated by real life as well as theoretical applications, have been developed over the time. One of the most studied ones are various types of edge-colorings.

Skip to content