Graph coloring problems with applications in algebraic logic. (English) Zbl 0753.05037

Tuza, Zs.

Acta Univ. Carol., Math. Phys. 32, No. 2, 55-60 (1991).

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.

MSC:

05C15	Coloring of graphs and hypergraphs
03G15	Cylindric and polyadic algebras; relation algebras

Keywords:

graph coloring problems; relation algebras; representation; algorithmic complexity