A1 Fei He

AD Grad. Sch. of Inf., Kyoto Univ., Kyoto

A1 H. Nagamochi

AD Grad. Sch. of Inf., Kyoto Univ., Kyoto

PB iet

T1 A method for generating colorings over graph automorphism

JN IET Conference Proceedings

SP 12 .

OP 12 .

AB 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.

K1 polynomial space

K1 coloring generation

K1 enumerated colorings

K1 Polya theorem

K1 chemical graph isomer

K1 polynomial delay

K1 graph automorphism

K1 axial symmetry

DO https://doi.org/10.1049/cp.2015.0611

UL https://digital-library.theiet.org/;jsessionid=3qt76lbhh8bph.x-iet-live-01content/conferences/10.1049/cp.2015.0611

LA English

SN

YR 2015

OL EN