About non-isomorphic graph colouring generating by read - faradzhev method

We consider the problem of generating all the non-isomorphic vertex k-colourings of a graph. The main point is to provide an algorithm for solving the problem without isomorphism testing technique proposed in Read - Faradzhev method. The algorithm is based on the backtracking method. Each iteration calculates the set of orbits for a given colouring, selects one representative from each orbit, and each representative is coloured in all colors in a selected way. From the set of colourings thus obtained, not canonical are cut off. The generation proceeds until canonical colourings remain.

Keywords

Authors

References