Structure theory and algorithms for highly regular colored graphs

Highly regular finite graphs are mesmerizing combinatorial objects. Their core characteristics exhibit how the structure of local subgraphs relates to the global structure of the whole graph. They have applications in various mathematical fields such as statistics, coding theory, and the general study of symmetries. We call a graph highly regular if it is k-ultrahomogeneous or ℓ-tuple regular for suitable k, ℓ ∈ N: a graph is k-ultrahomogeneous if every isomorphism between two induced subgraphs of order at most k extends to an automorphism of the entire graph. Further, it is ultrahomogeneous if it is simultaneously k-ultrahomogeneous for all k ∈ N. In contrast, a graph is ℓ-tuple regular if the number of common neighbors of a vertex set S of order at most ℓ only depends on the isomorphism type of the subgraph induced by S. These graph properties have been studied extensively in the past. Especially, 1-ultrahomogeneity and 2-tuple regularity are better known as vertex-transitivity and strong regularity, respectively. The focus of this thesis lies in the investigation of highly regular colored graphs. These naturally appear in the context of symmetries and graph isomorphism algorithms. For example, the well-studied Weisfeiler-Leman algorithms form a family of incomplete approaches to the graph isomorphism problem. They store combinatorial information on the local structure of a graph by coloring it. In particular, the ℓ-tuple regular colored graphs are closely related to the ℓ-dimensional Weisfeiler-Leman algorithm. The amount of information needed to distinguish a graph from non-isomorphic ones is measured by the Weisfeiler-Leman dimension. Altogether, colored graphs are a natural choice to examine for high regularity. In this thesis, we classify the ℓ-tuple regular vertex-colored undirected finite graphs and the k-ultrahomogeneous vertex-colored undirected finite graphs for ℓ ≥ 5 and k ≥ 4. In particular, this includes the classification of ultrahomogeneous vertex-colored undirected finite graphs. Beyond that, we exhaustively enumerate all k-ultrahomogeneous and ℓ-tuple regular arc-colored directed finite graphs of order at most 34. In recent years, the Weisfeiler-Leman dimension has become a standard measure of descriptive complexity of a graph. We establish a lower bound of 0.0105027 · n − o(n) and an upper bound of 0.15 · n + o(n) for the Weisfeiler-Leman dimension of n-vertex graphs. We reduce the claim for the upper bound to 2-tuple regular colored graphs. Given the complexity of their structure, we develop new techniques to facilitate their analysis. This includes conditions under which a vertex color class can be restored, up to isomorphism, if it is removed. Within our proof, we also derive an upper bound of 0.05 · n + o(n) on the Weisfeiler-Leman dimension of colored graphs whose color classes all have size at most 7.