2020/12/02 by Irene Heinrich, Thomas Schneider, Heinrich, Irene +3
Computer Science · Mathematics · #05B05 #05B20 #05C60 #05C75 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Limits and Structures in Graph Theory #math.CO #msc:05B05 #msc:05B20 #msc:05C60 #msc:05C75
paper · pdf · doi:10.48550/arxiv.2012.01058
34 pages, 2 figures
openalex publication_date 2020/12/02 · arxiv created 2021/02/22 · arxiv updated 2021/02/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A coloured graph is k-ultrahomogeneous if every isomorphism between two induced subgraphs of order at most k extends to an automorphism. A coloured graph is t-tuple regular if the number of vertices adjacent to every vertex in a set S of order at most k depends only on the isomorphism type of the subgraph induced by S. We classify the finite vertex-coloured k-ultrahomogeneous graphs and the finite vertex-coloured l-tuple regular graphs for k at least 4 and l at least 5, respectively. Our theorem in particular classifies finite vertex-coloured ultrahomogeneous graphs, where ultrahomogeneous means the graph is simultaneously k-ultrahomogeneous for all k.