Geodesic
About generation of non-isomorphic vertex $k$-colorings
Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 136-138 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In this paper, we study the generation problem for non-isomorphic vertex and edge $k$-colorings of a given graph. An algorithm for generating all the non-isomorphic vertex $k$-colorings of a graph by the Reed–Faradzhev method without using an isomorphism testing technique is suggested. The problem of generating edge $k$-colorings is reduced to the problem of generating vertex $k$-colorings.
Keywords: graph, coloring, vertex coloring.
Mots-clés : isomorphism 
@article{PDMA_2017_10_a52,
     author = {M. B. Abrosimov and P. V. Razumovsky},
     title = {About generation of non-isomorphic vertex $k$-colorings},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {136--138},
     year = {2017},
     number = {10},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2017_10_a52/}
}
TY  - JOUR
AU  - M. B. Abrosimov
AU  - P. V. Razumovsky
TI  - About generation of non-isomorphic vertex $k$-colorings
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2017
SP  - 136
EP  - 138
IS  - 10
UR  - http://geodesic.mathdoc.fr/item/PDMA_2017_10_a52/
LA  - ru
ID  - PDMA_2017_10_a52
ER  - 
%0 Journal Article
%A M. B. Abrosimov
%A P. V. Razumovsky
%T About generation of non-isomorphic vertex $k$-colorings
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2017
%P 136-138
%N 10
%U http://geodesic.mathdoc.fr/item/PDMA_2017_10_a52/
%G ru
%F PDMA_2017_10_a52
M. B. Abrosimov; P. V. Razumovsky. About generation of non-isomorphic vertex $k$-colorings. Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 136-138. http://geodesic.mathdoc.fr/item/PDMA_2017_10_a52/

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

[2] Kharari F., Teoriya grafov, Mir, M., 1973, 296 pp. | MR

[3] Nauty and Traces: Graph Canonical Labeling and Automorphism Group Computation, , 2016 http://users.cecs.anu.edu.au/~bdm/nauty/

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