Geodesic
About non-isomorphic graph colouring generating by Read–Faradzhev method
Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 173-176 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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: graph colouring, isomorphism rejection.
Mots-clés : graph isomorphism 
@article{PDMA_2019_12_a47,
     author = {M. B. Abrosimov and P. V. Razumovskii},
     title = {About non-isomorphic graph colouring generating by {Read{\textendash}Faradzhev} method},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {173--176},
     year = {2019},
     number = {12},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2019_12_a47/}
}
TY  - JOUR
AU  - M. B. Abrosimov
AU  - P. V. Razumovskii
TI  - About non-isomorphic graph colouring generating by Read–Faradzhev method
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2019
SP  - 173
EP  - 176
IS  - 12
UR  - http://geodesic.mathdoc.fr/item/PDMA_2019_12_a47/
LA  - ru
ID  - PDMA_2019_12_a47
ER  - 
%0 Journal Article
%A M. B. Abrosimov
%A P. V. Razumovskii
%T About non-isomorphic graph colouring generating by Read–Faradzhev method
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2019
%P 173-176
%N 12
%U http://geodesic.mathdoc.fr/item/PDMA_2019_12_a47/
%G ru
%F PDMA_2019_12_a47
M. B. Abrosimov; P. V. Razumovskii. About non-isomorphic graph colouring generating by Read–Faradzhev method. Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 173-176. http://geodesic.mathdoc.fr/item/PDMA_2019_12_a47/

[1] Hayes J. P., “A graph model for fault-tolerant computing system”, IEEE Trans. Comput., C.25:9 (1976), 875–884 | DOI | MR

[2] Abrosimov M. B., Grafovye modeli otkazoustoichivosti, Izd-vo Sarat. un-ta, Saratov, 2012, 192 pp.

[3] Brinkmann G., “Isomorphism rejection in structure generation programs”, Discrete Mathematical Chemistry, DIMACS Ser. Discr. Math. Theor. Comput. Sci., 51, 2000, 25–38 | DOI | MR | Zbl

[4] Abrosimov M. B., Razumovskii P. V., “O generatsii neizomorfnykh vershinnykh $k$-raskrasok”, Prikladnaya diskretnaya matematika. Prilozhenie, 2017, no. 10, 136–138

[5] McKay B. D., Nauty and Traces: Graph canonical labeling and automorphism group computation, , 2017 http://users.cecs.anu.edu.au/b̃dm/nauty/nug26.pdf

[6] McKay B. D., Piperno A., “Practical graph isomorphism”, J. Symbolic Computation, 2:60 (2013), 94–112 | MR