Projects / Programmes
Topological and metric graph theory
| Code |
Science |
Field |
Subfield |
| 1.01.00 |
Natural sciences and mathematics |
Mathematics |
|
| Code |
Science |
Field |
| P110 |
Natural sciences and mathematics |
Mathematical logic, set theory, combinatories |
graph, embedding, genus, edge-width, face-width, crossing number, minor, coloring, nowhere-zero flow, distance, convexity, discrete metric space, Cartesian product, direct product, median graph, partial cube, isometric subgraph, automorphism
Researchers (25)
Organisations (1)
Abstract
The first part of the project we shall primarily consider properties of embedded graphs. In particular, we will investigate locally planar embeddings with special emphasis on edge-width, face-width and their generalization - the nonseparating width. In connection to the theory of graph minors we shall pay our interest towards crossing number of graphs, unavoidable structures in large graphs, and forbidden minor characterizations of certain minor closed graph classes. We shall also study spectral properties of (embedded) graphs with respect to the discrete Laplacian operator. Further, we shall investigate graph colorings, in particular list colorings, circular chromatic number, and nowhere-zero flows in graphs.
In the second part of the project we shall investigate classes of graphs that are defined by metric properties or for which there exists a factorization with respect to graph products. Factorizations of hypercubes with respect to the direct product will be studied, as well as conditions under which this kind of factorization could be generalized to Cartesian product graphs and median graphs. We shall study partial cubes, their subclasses related to median graphs, and the subclass of regular partial cubes. In relation with the graceful trees conjecture we shall introduce a new labeling of partial cubes and study the question whether all partial cubes admit the generalized graceful labeling. Cube polynomial for median graphs will be further investigated, and relations between the zeros of this polynomial and important classes of median graphs will be considered. We shall study graph invariants of graph products, in particular the multiple domination, and investigate relations of obtained results with the Vizing conjecture on domination number of Cartesian product graphs.
