Projects / Programmes
Contemporary invariants of graphs
| Code |
Science |
Field |
Subfield |
| 1.01.00 |
Natural sciences and mathematics |
Mathematics |
|
| Code |
Science |
Field |
| P110 |
Natural sciences and mathematics |
Mathematical logic, set theory, combinatories |
| Code |
Science |
Field |
| 1.01 |
Natural Sciences |
Mathematics |
graph coloring, graph domination, vertex cover, metric dimension, domination game, coloring game, games on graphs
Researchers (17)
Organisations (2)
Abstract
Graph theory is a fast-growing area of modern mathematics, and the study of graph invariants one of its inherent parts. In this project, we consider some of the problems concerning classical concepts in graph theory, and combine their investigations in a natural way with the study of recently introduced and often applicable graph parameters. Some of the more recent invariants that we consider are motivated by practical problems and applications, others were introduced while searching for tools to attack important open conjectures. The studied invariants can be divided into several types, namely, coloring invariants, domination invariants, covering invariants, dimension invariants and game invariants of graphs.
Main objectives of the project are the following:
(1) To give new insights and possibly solutions to well-known open problems and conjectures. The study will include versions of domination numbers of the Cartesian product of graphs (Vizing's conjecture and Vizing-type results), the chromatic number of the direct product of graphs (Hedetniemi's conjecture), L(2,1) colorings of graphs with bounded degree (conjecture of Griggs and Yeh), b-chromatic numbers of regular graphs (Erdős-Farber-Lovász conjecture), the domination number of planar near triangulations (Matheson-Tarjan conjecture), the vertex k-path cover numbers of planar graphs (a weak version of the Albertson-Berman conjecture), covering a graph with geodesic paths (in relation with Meyniel's conjecture), the conjectures on the game (total) domination numbers, open problems on the game chromatic number and its variations.
(2) To advance the investigations of some recently introduced invariants on graphs, and give significant advances in their studies.
The invariants include, but are not restricted to, different coloring and (rainbow) domination invariants, b-chromatic numbers, (relaxed) L(j,k) labelings, the packing chromatic number, various covering invariants (in particular, the vertex k-path cover number and the strong geodetic number), different types of metric dimensions of graphs, and invariants arising from games on graphs, such as the game chromatic number, the indicated chromatic number, the game Grundy number, and the game (total) domination numbers.
(3) A comprehensive study of some interrelated groups of concepts, which will result in at least two survey papers. In the surveys we plan to identify and emphasize central open problems as well as pose new open problems. Such a survey papers are expected to have a large impact on the related research areas. We will concentrate on several areas:
(i) domination game(s), for which we plan to write a monograph;
(ii) packing colorings and related distance coloring concepts;
(iii) domination-type invariants and their behavior on Cartesian products of graphs (Vizing-type results).
(4) We plan to write a monograph on the domination game(s), which in recent years (the game was introduced only in 2010) became one of the most extensively investigated games on graphs. The book will be written by the combination of two members of the project group and two external colleagues, all of whom have been involved in the study of domination game(s) from the very beginning.
Significance for science
The project belongs to basic research in the area of mathematics and with its applicable aspects touches some related fields such as computer science. Problems that we will work on are internationally important, which can be justified by our publications from the last period as well as with the impact of our results. We plan to attack some important long-standing mathematical problems, whose (complete or even partial) solutions would have considerable impact on research developments in graph theory and related areas.
The problems that we propose to investigate are not only unsolved, but having in mind the number of established mathematicians that have considered them they are also relevant.
In some cases, the problems are related to other mathematical disciplines (such as to linear algebra in the case of zero forcing numbers) and in some other cases they are connected to other (applicable) scientific areas (such as in the case of L(j,k) labelings, metric dimensions and others). We expect to publish several papers in key journals from the area of discrete mathematics related to the topics of the proposed project. We will also present our results at relevant international conferences.
The work on the project will also serve as a perfect support for the monograph concerning domination game(s), which is a desirable and realistic goal of the project, This can be justified by the quick development of the area, and a number of responses that a monograph about the important instance of graph game(s) would in a natural way be placed in the (non-empty) space between graph theory and combinatorial game theory.
Significance for the country
The project belongs to basic research in the area of mathematics and with its applicable aspects touches some related fields such as computer science. Problems that we will work on are internationally important, which can be justified by our publications from the last period as well as with the impact of our results. We plan to attack some important long-standing mathematical problems, whose (complete or even partial) solutions would have considerable impact on research developments in graph theory and related areas.
The problems that we propose to investigate are not only unsolved, but having in mind the number of established mathematicians that have considered them they are also relevant.
In some cases, the problems are related to other mathematical disciplines (such as to linear algebra in the case of zero forcing numbers) and in some other cases they are connected to other (applicable) scientific areas (such as in the case of L(j,k) labelings, metric dimensions and others). We expect to publish several papers in key journals from the area of discrete mathematics related to the topics of the proposed project. We will also present our results at relevant international conferences.
The work on the project will also serve as a perfect support for the monograph concerning domination game(s), which is a desirable and realistic goal of the project, This can be justified by the quick development of the area, and a number of responses that a monograph about the important instance of graph game(s) would in a natural way be placed in the (non-empty) space between graph theory and combinatorial game theory.
Most important scientific results
Interim report
Most important socioeconomically and culturally relevant results
