zbMATH — the first resource for mathematics

Graph coloring problems with applications in algebraic logic. (English) Zbl 0753.05037
Summary: For symmetric atomic relation algebras the property of being representable, finitely representable, or associative (when associativity is not supposed to hold by definition) is known to be equivalent to the existence of some edge colorings of complete graphs. Here we give a short survey of open problems and related results concerning necessary and sufficient conditions, unicity of a representation, and the algorithmic complexity of deciding those properties.

05C15 Coloring of graphs and hypergraphs
03G15 Cylindric and polyadic algebras; relation algebras
Full Text: EuDML