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 
topological graph theory, graph coloring, graph products, metric graph theory, theory of algorithms, graph minor, connectivity, discrete geometry.
Evaluation (rules)
source: COBISS
Researchers (19)
no. Code Name and surname Research area Role Period No. of publicationsNo. of publications
1.  22402  PhD Drago Bokal  Mathematics  Researcher  2004 - 2008  238 
2.  17005  PhD Boštjan Brešar  Mathematics  Researcher  2004 - 2008  403 
3.  25993  PhD Sergio Cabello Justo  Mathematics  Researcher  2006 - 2008  218 
4.  29585  PhD Rok Erman  Mathematics  Junior researcher  2008  14 
5.  16332  PhD Gašper Fijavž  Mathematics  Researcher  2004 - 2008  121 
6.  11220  PhD Martin Juvan  Mathematics  Researcher  2004 - 2008  235 
7.  05949  PhD Sandi Klavžar  Mathematics  Researcher  2004 - 2008  1,175 
8.  25571  PhD Matjaž Kovše  Mathematics  Junior researcher  2005 - 2008  77 
9.  13351  PhD Alenka Lipovec  Educational studies  Researcher  2004 - 2008  512 
10.  08727  PhD Uroš Milutinović  Mathematics  Researcher  2004 - 2008  348 
11.  01931  PhD Bojan Mohar  Mathematics  Head  2004 - 2008  1,002 
12.  20839  PhD Iztok Peterin  Mathematics  Researcher  2006 - 2008  350 
13.  16013  PhD Ciril Petr  Mathematics  Researcher  2005 - 2008  68 
14.  22649  PhD Janez Povh  Computer intensive methods and applications  Researcher  2007 - 2008  341 
15.  15518  PhD Riste Škrekovski  Mathematics  Researcher  2004 - 2008  506 
16.  24904  PhD Simon Špacapan  Mathematics  Researcher  2008  109 
17.  11666  PhD Aleksander Vesel  Computer intensive methods and applications  Researcher  2004 - 2008  338 
18.  24049  PhD Andrej Vodopivec  Mathematics  Researcher  2005 - 2008  14 
19.  18504  PhD Petra Žigert Pleteršek  Mathematics  Researcher  2004 - 2008  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 from the area of mathematics. Problems that we will work on are internationally important, which can in particular be justified with 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. We expect that the newly obtained results will be published in established international journals and we will present them at international scientific conferences. For the next period we expect that we will be invited to deliver several invited plenary talks which will further emphasize the importance of ourresearch achievements. In this way we will further increase the role of the Slovenian graph theory school. The results are mainly theoretical with potential to be applicable in information technologies. Our previous contacts with industry include Hermes Softlab and Iskratel. The research programme is oriented such that it enables to integrate the most promising young researchers. In this way it enables a long-term continuation of the quality research in mathematics which has in turn a positive influence on the quality of the university programs in mathematics. Since mathematics is used in many other areas, the quality of research in mathematics has an indirect but imporatant influence on the development of other disciplines as well. Inside mathematics the programme mostly developes graph theory and keeps and strenthens its world level. There is a strong international cooperation through bilateral projects and many research visits. In the last years we had the following international projects: 1. Cooperation with ALCOM (Pierre Rosenstiehl, France). 2. Cooperation with Hungarian Academy of Sciences. 3. Cooperation within European network DIMANET for discrete mathematics. 4. SLO-USA projects on graph minors (Neil Robertson, John Maharry, Ohio State University, USA). 5. Several bilateral projects with Austria (University of Leoben). 6. Several PROTEUS projects with IMAG, Grenoble, France (Sylvain Gravier and Michel Mollard). 7. SLO-DE project with the Technical University Ilmenau, Germany (Thomas Bohme and Michael Stiebitz). Every four years we organize an important international conference in graph theory (Slovenian Graph Theory Conference) with 100-200 participants from all over the world.
Significance for the country
Reserach of this program group is basic but the methods can be applied to optimization, network designs, control of production processes. Our expertise has led to a cooperation with the Slovenian industry from the technological development, mostly in the information and telecommunication technology. In the last period we have successfully cooperated in the projects Models and algorithms for employee scheduling (project ordered by HIT d.d., Nova Gorica), Algorithms for developing a model of working process (project ordered by ICIT, d.o.o., Šempeter pri Gorici), Optimal distribution among fuel stations (project ordered be Ultra d.o.o., Zagorje ob Savi), The application of the Q factor (SAIDI and SAIFI) in the methodology of determining distribution charges for power transmission and distribution grid (the project is done in collaboration with the institute Milan Vidmar), Graphs and telecommunication networks (IMFM and ISKRATEL, telekomunikacijski sistemi, d.o.o.), Graph minors, graphs on surfaces and networks (IMFM and Hermes Softlab Programska Oprema).
Most important scientific results Final report, complete report on dLib.si
Most important socioeconomically and culturally relevant results Final report, complete report on dLib.si
Views history