Projects / Programmes source: ARIS

Graph Theory

Research activity

Code Science Field Subfield
1.01.00  Natural sciences and mathematics  Mathematics   
1.07.00  Natural sciences and mathematics  Computer intensive methods and applications   
2.07.00  Engineering sciences and technologies  Computer science and informatics   

Code Science Field
P110  Natural sciences and mathematics  Mathematical logic, set theory, combinatories 

Code Science Field
1.01  Natural Sciences  Mathematics 
topological graph theory, graph coloring, graph products, metric graph theory, theory of algorithms, graph minor, connectivity, discrete geometry.
Evaluation (rules)
source: COBISS
Researchers (34)
no. Code Name and surname Research area Role Period No. of publicationsNo. of publications
1.  35352  PhD Jernej Azarija  Mathematics  Junior researcher  2012 - 2014  25 
2.  22402  PhD Drago Bokal  Mathematics  Researcher  2009 - 2014  238 
3.  17005  PhD Boštjan Brešar  Mathematics  Researcher  2009 - 2014  403 
4.  25993  PhD Sergio Cabello Justo  Mathematics  Researcher  2009 - 2014  218 
5.  23411  PhD Jože Dedič  Mathematics  Researcher  2014  38 
6.  32028  PhD Tanja Dravec  Mathematics  Researcher  2009 - 2014  143 
7.  29585  PhD Rok Erman  Mathematics  Junior researcher  2009 - 2012  14 
8.  16332  PhD Gašper Fijavž  Mathematics  Researcher  2009 - 2014  121 
9.  34564  PhD David Gajser  Mathematics  Junior researcher  2011 - 2014  33 
10.  29919  PhD Marko Jakovac  Mathematics  Researcher  2011 - 2014  160 
11.  24751  PhD Janja Jerebic  Administrative and organisational sciences  Researcher  2011 - 2014  116 
12.  11220  PhD Martin Juvan  Mathematics  Researcher  2009 - 2012  235 
13.  05949  PhD Sandi Klavžar  Mathematics  Head  2009 - 2014  1,175 
14.  22401  PhD Matjaž Konvalinka  Mathematics  Researcher  2011  115 
15.  25571  PhD Matjaž Kovše  Mathematics  Researcher  2009 - 2012  77 
16.  22648  PhD Tadeja Kraner Šumenjak  Mathematics  Researcher  2010 - 2014  118 
17.  34562  PhD Matjaž Krnc  Mathematics  Junior researcher  2011 - 2014  93 
18.  13351  PhD Alenka Lipovec  Educational studies  Researcher  2009 - 2012  512 
19.  37403  PhD Tilen Marc  Mathematics  Junior researcher  2014  46 
20.  30823  PhD Gašper Mekiš  Mathematics  Researcher  2010 - 2013  17 
21.  08727  PhD Uroš Milutinović  Mathematics  Researcher  2009 - 2014  348 
22.  01931  PhD Bojan Mohar  Mathematics  Researcher  2009 - 2014  1,002 
23.  20839  PhD Iztok Peterin  Mathematics  Researcher  2009 - 2014  350 
24.  16013  PhD Ciril Petr  Mathematics  Researcher  2009 - 2014  68 
25.  22649  PhD Janez Povh  Computer intensive methods and applications  Researcher  2009 - 2012  341 
26.  33289  Vanja Svetina  Biology  Technical associate  2011 
27.  15518  PhD Riste Škrekovski  Mathematics  Researcher  2009 - 2012  506 
28.  24904  PhD Simon Špacapan  Mathematics  Researcher  2009 - 2014  109 
29.  21821  PhD Andrej Taranenko  Mathematics  Researcher  2010 - 2014  130 
30.  23904  PhD Aleksandra Tepeh  Mathematics  Researcher  2010 - 2013  131 
31.  11666  PhD Aleksander Vesel  Computer intensive methods and applications  Researcher  2009 - 2014  338 
32.  24049  PhD Andrej Vodopivec  Mathematics  Researcher  2009 - 2012  14 
33.  33306  PhD Sara Sabrina Zemljič  Mathematics  Junior researcher  2010 - 2014  19 
34.  18504  PhD Petra Žigert Pleteršek  Mathematics  Researcher  2009 - 2014  174 
Organisations (1)
no. Code Research organisation City Registration number No. of publicationsNo. of publications
1.  0101  Institute of Mathematics, Physics and Mechanics  Ljubljana  5055598000  19,658 
The research of the program group covers a considerable part of graph theory and its applications in other parts of mathematics and in other fields of research. The majority of the research will be given in the following areas. Basic properties of graph embeddable in surfaces will be explored. We will try to characterize obstructions for the existence of embeddings and to develop efficient embedding algorithms. In the theory of graph minors we plan to research the crossing number, unavoidable structures in large graphs, and forbidden minors for some minor closed families. We will investigate spectral properties of (embedded) graphs, mostly with respect to the Laplacian graph operator. We will also consider graph colorings, above all list colorings, nonrepetitive colorings, circular chromatic numbers, flows in graphs, and similar. Graph products will also be considered, in particular their invariants and related problems. Median graphs will be studied with an emphasis on the recognition problem. We will also consider several natural classes of graphs that appear naturally in the theory of median graphs: isometric subgraphs of hypercubes, semi-median graphs, quasi-median graphs and isometric subgraphs of Hamming graphs. Metric graph theory will be applied in the chemical graph theory in order to compute different topological invariants of graphs. In the area of computer mathematics we especially plan to develop fast algorithms for recognition of important graph classes and to study problems related to generalizations of the classical Tower of Hanoi problem. In cooperation with the University of Auckland from New Zealand we will perform an extensive computer work on a network with more than 200 computers in order to examine some well-known conjectures.
Significance for science
The project belongs to basic research in the area of mathematics. Problems on which we have been working on on are internationally important, which can in particular be justified by our bibliography from the last period as well as with the (citation) impact of our results. The problems are central in the area of graph theory and at the same time have applications in other scientific fields. For instance, our results on carbon nanotubes can accelerate the synthesis of carbon nanomolecules and therefore help the improvement of nanomaterials. Distances between graphs are used in those areas of science where similarities of objects are studied. New insights concerning distances between graphs further develop existing areas and give a fresh look at existing problems, specifically in areas like biology, computer science, chemistry, social sciences and linguistics. The study of graph invariants addresses some important real-life problems. In particular, the frequency assignment problem asks for assigning frequencies to transmitters in a wireless network. In a broadcasting network, each transmitter is assigned a frequency channel for its transmissions. Two transmissions can interfere if their channels are too close. This means that even if two transmitters use different channels, there still may be interference if the two transmitters are located close to each other. The spectrum of frequencies gets more and more scarce, because of increasing demands. Thus the task is to minimize the span of frequencies while avoiding interference. The obtained results were published in leading journals from the area of discrete mathematics and were presented at international scientific conferences. We were invited plenary speakers at numerous important international conferences. In this way we have further increased the international role of the Slovenian graph theory school.
Significance for the country
The research programme is oriented to encourage the integration of the most promising young researchers. In this way it enables a long-term continuation of the research quality in mathematics, which in turn has a positive influence on the quality of the university programs in mathematics and other sciences. In the period 2009-2014 we have supervised 9 Ph.D. students. After finishing their Ph.D., our students are getting employed also in industry, hence our programme has a positive impact on the national economy. Since mathematics is used in many other areas, the quality of research in mathematics has an indirect but important influence on the development of other disciplines as well. Inside mathematics the programme mostly develops graph theory and keeps and strengthens its world reputation. The expected results are mostly theoretical. Nevertheless, they have a big potential for applications, especially our research in algorithmic and optimization aspects of graph theory. This can be well justified with our previous research that has led to a cooperation with the Slovenian industry focused on technological development, mostly in the information and telecommunication technology. In June 2015 we will organize the “8th Slovenian International Conference on Graph Theory”, where we expect about 200-300 participants. This is one of the largest conferences in the world on graph theory. Our programme group will lead the organization, in particular, the programme leader is the main organizer of the event.
Audiovisual sources (1)
no. Title (with video link) Event Source
1. Graph Theory    Research programme video presentation 
Most important scientific results Annual report 2009, 2010, 2011, 2012, 2013, final report, complete report on dLib.si
Most important socioeconomically and culturally relevant results Annual report 2009, 2010, 2011, 2012, 2013, final report, complete report on dLib.si
Views history