Projects / Programmes
January 1, 2009
- December 31, 2014
| 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.
Researchers (34)
Organisations (1)
Abstract
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
