A method for generating colorings over graph automorphism

Given a graph G = (V, E) with a set W ⊆ V of vertices, we enumerate colorings to W such that for every two enumerated colorings c and c´ the corresponding colored graphs (G, c) and (G, c´) are not isomorphic. This problem has an important application in the study of isomers of chemical graphs such as generation of benzen isomers from a tree-like chemical graph structure. The number of such colorings can be computed efficiently based on Polya´s theorem. However, enumerating each from the set of these colorings without using a large space is a challenging problem in general. In this paper, we propose a method for enumerating these colorings when the automorphisms of G are determined by two axial symmetries, and show that our algorithm can be implemented to run in polynomial delay and polynomial space.