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|