%0 Electronic Article
%A Fei He
%+ Grad. Sch. of Inf., Kyoto Univ., Kyoto
%A H. Nagamochi
%+ Grad. Sch. of Inf., Kyoto Univ., Kyoto
%K polynomial space
%K coloring generation
%K enumerated colorings
%K Polya theorem
%K chemical graph isomer
%K polynomial delay
%K graph automorphism
%K axial symmetry
%X 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.
%T A method for generating colorings over graph automorphism
%B IET Conference Proceedings
%D January 2015
%P 12 .-12 .
%I Institution of Engineering and Technology
%U https://digital-library.theiet.org/;jsessionid=37rkd43fb0bcp.x-iet-live-01content/conferences/10.1049/cp.2015.0611
%G EN