Research project is (co) funded by the Slovenian Research Agency.
UL Member: Faculty of Mathematics and Physics
Code: J1-1692
Project: Graph Colorings, Decompositions and Coverings
Period: 1. 7. 2019 - 30. 6. 2022
Range per year: 1,45 FTE, category: C
Head: Riste Škrekovski
Research activity: Natural sciences and mathematics
Citations for bibliographic records
Project description:
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.
