Loading...
Projects / Programmes source: ARIS

Graph Colorings, Decompositions and Coverings

Research activity

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 
Keywords
graph coloring, flow, decomposition, covering, factor, T-join
Evaluation (rules)
source: COBISS
Researchers (22)
no. Code Name and surname Research area Role Period No. of publicationsNo. of publications
1.  31774  PhD Klen Čopič Pucihar  Computer science and informatics  Researcher  2019 - 2022  147 
2.  50728  PhD Darko Dimitrov  Mathematics  Researcher  2019 - 2022  78 
3.  55262  PhD Tomislav Došlić  Mathematics  Researcher  2022  82 
4.  29665  PhD Rija Erveš  Mathematics  Researcher  2019 - 2022  52 
5.  35875  Marjeta Grahek    Technical associate  2020 - 2022 
6.  38085  PhD Petr Gregor  Mathematics  Researcher  2019 - 2022  40 
7.  33510  PhD Jelena Klisara  Mathematics  Researcher  2019 - 2022  16 
8.  24897  PhD Matjaž Kljun  Computer science and informatics  Researcher  2019 - 2022  172 
9.  36238  PhD Martin Knor  Mathematics  Researcher  2019 - 2022  117 
10.  34562  PhD Matjaž Krnc  Mathematics  Researcher  2019 - 2022  94 
11.  27800  PhD Zoran Levnajić  Physics  Researcher  2019 - 2022  135 
12.  31670  PhD Borut Lužar  Computer intensive methods and applications  Researcher  2019 - 2022  183 
13.  55615  PhD Mirko Petrushevski  Mathematics  Researcher  2021 - 2022  33 
14.  18838  PhD Primož Potočnik  Mathematics  Researcher  2019 - 2022  238 
15.  37541  PhD Alejandra Ramos Rivera  Mathematics  Researcher  2021 - 2022  18 
16.  32250  PhD Polona Repolusk  Interdisciplinary research  Researcher  2020  45 
17.  55478  PhD Jelena Sedlar  Mathematics  Researcher  2022  25 
18.  36239  PhD Roman Sotak  Mathematics  Researcher  2019 - 2022  62 
19.  15518  PhD Riste Škrekovski  Mathematics  Head  2019 - 2022  508 
20.  53598  PhD Kenny Štorgel  Mathematics  Junior researcher  2020 - 2022  21 
21.  23904  PhD Aleksandra Tepeh  Mathematics  Researcher  2019 - 2022  132 
22.  30920  PhD Janoš Vidali  Mathematics  Researcher  2019 - 2022  26 
Organisations (2)
no. Code Research organisation City Registration number No. of publicationsNo. of publications
1.  1554  University of Ljubljana, Faculty of Mathematics and Physics  Ljubljana  1627007  34,059 
2.  2784  Faculty of Information Studies in Novo mesto  Novo mesto  3375650  6,110 
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
Views history
Favourite