Congruences and subdirect representations of graphs

Stefan Veldsman (Department of Mathematics, Nelson Mandela University, Port Elizabeth, South Africa)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 8, No 1 (2020): Electronic Journal of Graph Theory and Applications

A basic tool in universal algebra is that of a congruence. It has been shown that congruences can be defined  for graphs with properties similar to their universal algebraic counterparts. In particular, a subdirect product of graphs and hence also a subdirectly irreducible graph, can be expressed in terms of graph congruences. Here the subdirectly irreducible graphs are determined explicitly. Using congruences, a graph theoretic version of the well-known Birkhoff Theorem from universal algebra is given. This shows that any non-trivial graph is a subdirect product of subdirectly irreducible graphs