×

Antivarieties and colour-families of graphs. (English) Zbl 1058.08009

The authors suggest an algebraic approach to the study of colour-families of graphs. This approach is based on the notion of a congruence of an arbitrary structure. They prove that every colour-family of graphs is a finitely generated universal Horn class and show that for every colour-family the universal theory is dedicable. They study the structure of the lattice of colour-families of graphs and the lattice of antivarieties of graphs. They also consider bases of quasi-identities and bases of anti-identities for colour-families and find certain relations between the existence of bases of a special form and problems in graph theory.

MSC:

08C15 Quasivarieties
03B25 Decidability of theories and sets of sentences
05C15 Coloring of graphs and hypergraphs
05C75 Structural characterization of families of graphs
03C05 Equational classes, universal algebra in model theory
PDFBibTeX XMLCite