Thursday, 16.08.2018
15:00

16:00
Colour refinement is a basic algorithm for graph isomorphism testing. It splits the vertex set of a graph until all vertices
in a class have the same number of neighbours in every other class. The resulting partition is called (coarsest) equitable
partitionof a graph.
Tinhofer, Ramana et al. and Godsil found a tight connection between equitable partitions of a graph and fractional automorphisms,
which are the LP relaxation of the natural ILP formulation of graph isomorphism.
Grohe et al. generalised the colour refinement algorithm for weighted bipartite graphs in a matrix representation and they
introduced a theory of equitable partitions, fractional automorphisms and fractional isomorphisms for weighted bipartite graphs
in a matrix representation.
We develop a series of generalisations and extensions of their theory.
Firstly, we modify the colour refinement algorithm to work on weighted directed graphs in matrix representation. Furthermore,
we extend the theory of equitable partitions, fractional automorphisms and fractional isomorphisms to weighted directed graphs.
Secondly, we adapt the results for graphs with an additional weighted unary or binary relation. Then we adapt Atserias’ and
Maneva’s definition of kequitable partitions to state the kdimensional colour refinement algorithm for weighted directed
graphs.
Thirdly, we generalise kequitable partitions and kdimensional colour refinement to weighted τstructures.
In the end, we state a general theorem on the consistent theory of equitable partitions, fractional automorphisms and fractional
isomorphisms.