Varieties of graphoids and Birkoff’s theorem for graphs

Abstract

The algebraic structure of graphoids is used in order to obtain the wellknown Birkhoff’s theorem in the framework of graphs. Namely we establish a natural bijection between the class of Σ-graphoids and the class of strong congruences over GR(Σ, X), which is the free graphoid over the doubly ranked alphabet Σ and the set of variables X.