Classification of Finite Highly Regular Vertex-Coloured Graphs
From MaRDI portal
Publication:6355115
arXiv2012.01058MaRDI QIDQ6355115FDOQ6355115
Authors: Irene Heinrich, Thomas D. Schneider, P. Schweitzer 
Publication date: 2 December 2020
Abstract: 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.
Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Combinatorial aspects of block designs (05B05) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Structural characterization of families of graphs (05C75)
This page was built for publication: Classification of Finite Highly Regular Vertex-Coloured Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6355115)
