On the problem of domino recognition

A linear algorithm for domino and linear domino recognition and constructing the list of maximal cliques of such graphs is proposed. Unlike the algorithm in [Kloks, T., D. Kratsch and H. Muller, Dominoes, Workshop on Graph-Theoretic Concepts in Computer Science, 1994, 106–120] it doesnʹt require preliminary analysis of a graph. The characterizations of a domino and a linear domino are given in term of special clique covering existence.