Projects / Programmes
Graph Colorings, Decompositions and Coverings
| Code |
Science |
Field |
Subfield |
| 1.01.05 |
Natural sciences and mathematics |
Mathematics |
Graph theory |
| Code |
Science |
Field |
| P110 |
Natural sciences and mathematics |
Mathematical logic, set theory, combinatories |
| Code |
Science |
Field |
| 1.01 |
Natural Sciences |
Mathematics |
graph coloring, flow, decomposition, covering, factor, T-join
Researchers (22)
Organisations (2)
Abstract
Since its humble beginnings from almost 300 years ago, during the last half a century the field of Graph Theory has undergone tremendous growth and has become one of the main areas of contemporary scientific research within mathematics. Supported by its evident applicability in technology, the area continues to grow, and due achievements of recent years we are witnessing a treasure trove of results, methods, ideas and problems. Over the past few decades the Slovenian School of Graph Theory has had an influential role in the development of this mathematical discipline on global level, to the extent that its international recognition nowadays is comparable to those of similar Schools from the technologically most developed countries worldwide.
Our project proposal concentrates on certain aspects of chromatic graph theory. A fundamental process in mathematics is that of partitioning a set of objects into classes according to certain rules. Chromatic graph theory deals with a situation where a discrete object is partitioned into simpler sub-objects. However, the simplicity of the rules does not mean that the problems encountered are simple - on the contrary. Within the framework of the intended research, our focus will be on two modern and promising research topics in the field of edge-colorings and coverings of graphs.
The first (resp. second) topic studies the possibilities for imposing global parity regularity (resp. local irregularity) on graphs via coloring their edge sets. Our current interest in the first of these themes stems from an old result (dating from 1978) that established a connection between nowhere-zero flows and edge-coverings by even subgraphs. This part of the project would be a continuation of our ongoing study of odd edge-colorings (resp. coverings) of graphs as well as of their generalization called vertex-parity edge-colorings (resp. coverings). The inception of the second topic dates to 1986 and is related to the concept known as irregularity strength of a graph. It has generated a significant amount of scientific interest in the last $15$ years, resulting with three well known conjectures: the 1-2-3 Conjecture (2004), the Detection Conjecture (2005), and the Local Irregularity Conjecture (2015). Each of the three conjectures refers to the minimum number of colors needed for, respectively, neighbor sum distinguishing, neighbor multiset distinguishing, and locally irregular edge-coloring of a given `colorable' graph. Perhaps resolving these conjectures is still beyond what can be achieved with current knowledge. Thus we initially intend to study certain aspects of these conjectures only for restricted families of graphs.
Although there does not seem to be any apparent relationship between the colorings arising in the first and in those arising in the second of the proposed topics, just recently a result on vertex-parity edge-colorings has been used to obtain the currently best general upper bound on the (locally) irregular chromatic index. We plan a more systematic study of the `touching ends' of this bridging to discover if more lies hidden below the surface. As is quite often the case, research on variations of coloring problems tends to provide better insight into the original problems. Therefore, an additional part of the project will concentrate on the study of list and covering variants of the mentioned coloring notions.
Significance for science
Graph theory is a modern branch of mathematics, which has expanded significantly during the last century due to the enormous progress of technology, and it is widely applied in many diverse sciences such as algorithms in computer science, modeling molecules in chemistry, modeling communication networks, and studying complex networks. The chromatic graph theory, with its origins starting in 1852, is nowadays central and major part of graph theory. In the scope of the project, we will consider problems from chromatic graph theory which are closely related with the flow theory, graph decompositions and related thematics, which are currently hot topics in modern graph theory. By publishing our results in the scientific journal of the highest rank, presentations on international conferences and on seminars of foreign research groups, we will introduce the problematics to wider set of researchers. Our already published results show that these types of problems are interesting for various groups of researchers as our papers, yet recent, have already obtained a considerable number of citations.
Significance for the country
Graph theory is a modern branch of mathematics, which has expanded significantly during the last century due to the enormous progress of technology, and it is widely applied in many diverse sciences such as algorithms in computer science, modeling molecules in chemistry, modeling communication networks, and studying complex networks. The chromatic graph theory, with its origins starting in 1852, is nowadays central and major part of graph theory. In the scope of the project, we will consider problems from chromatic graph theory which are closely related with the flow theory, graph decompositions and related thematics, which are currently hot topics in modern graph theory. By publishing our results in the scientific journal of the highest rank, presentations on international conferences and on seminars of foreign research groups, we will introduce the problematics to wider set of researchers. Our already published results show that these types of problems are interesting for various groups of researchers as our papers, yet recent, have already obtained a considerable number of citations.
Most important scientific results
Interim report
Most important socioeconomically and culturally relevant results
