Thomas Schneider

(AG Algorithmics and Complexity, Prof. Schweitzer)
hosted by PhD Program in CS @ TU KL

"Classification of Finite Highly Regular Vertex-Coloured Graphs"

In the literature, there are two concepts describing the "high regularity" of graphs: First, a graph is k-ultrahomogeneous if every isomorphism between two induced subgraphs of order at most k extends to an automorphism. Next, a graph is k-tuple regular if for any vertex set S of order at most k the amount of common neighbours only depends on the isomorphism type of the subgraph induced by S. In this talk, I give an overview of the existing classification results of undirected uncoloured graphs. After extending both properties above to coloured graphs, I present our classification of finite vertex-coloured k-ultrahomogeneous graphs and finite vertex-coloured k-tuple regular graphs for k >= 4.

Time:	Monday, 11.01.2021, 15:45
Place:
Video:

Termin als Datei downloaden und in den Kalender importieren.