Login
English      Slovensko
print

Customized Project N1-0102
Topics in Structural Graph Theory: Invariants, Separators, and Intersection Representations

 

Project Title: Topics in Structural Graph Theory: Invariants, Separators, and Intersection Representations

PI: Martin Milanič

Project Code: N1-0102.

Type of the Project: customized project.

Funding Organization: Slovenian Research Agency (ARRS).

Research Field (ARRS): 1.01.00 - Natural Sciences and Mathematics / Mathematics.

Duration: 1. 5. 2019 - 30. 4. 2022.

Project Category: B.

Yearly Range: 1.30 FTE (2202 research hours).

Sicris profile of the project is here.

Research Organization: University of Primorska, Andrej Marušič Institute.

Project Members:

Abstract:

Practical and theoretical issues stemming from the many application areas of graph theory motivate the development of fast algorithms for computing, either exactly or approximately, various graph invariants, such as chromatic number, clique number, and independence number. As the corresponding optimization problems are typically intractable, understanding the relations between the invariants becomes of crucial importance for identifying the easy cases; these are described using the notion of graph classes. Despite a number of recent breakthrough developments in the area, many deep and challenging questions remain.

The project will investigate several key problems within pure and algorithmic graph theory, with a focus on graph invariants and graph classes. It will be developed along three interconnected research lines: conditions for the existence of a function bounding one invariant in terms of another one, algorithmic aspects of selected graph optimization problems on various graph classes, and the development of a unifying framework for generalizations of chordality. Progress on these problems is expected to be obtained using an effective combination of various complementary concepts and techniques suitable for the study of graph classes such as: graph decompositions, graph width parameters, minimal separators, graph minors, extremal graph theory.

We will pay particular attention to the study of some poorly understood aspects of the theory, such as relations between Hadwiger number and other invariants, representability of graphs as intersection graphs of graphs of small treewidth, and sufficient conditions for tractability of Independent Set and related problems. The final goal of this project is the development of new tools for a deep and algorithmically useful mathematical analysis of the structure of graphs in hereditary classes. Its impact will be an improved fundamental understanding of the boundaries of tractability for several practically relevant graph optimization problems.