Geodesic
The NP-completeness of automorphic colorings
Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 4, pp. 705-710

Voir la notice de l'article provenant de la source Library of Science

Given a graph G, an automorphic edge(vertex)-coloring of G is a proper edge(vertex)-coloring such that each automorphism of the graph preserves the coloring. The automorphic chromatic index (number) is the least integer k for which G admits an automorphic edge(vertex)-coloring with k colors. We show that it is NP-complete to determine the automorphic chromatic index and the automorphic chromatic number of an arbitrary graph.
Keywords: NP-complete problems, chromatic parameters, graph coloring, computational complexity 
@article{DMGT_2010_30_4_a14,
     author = {Mazzuoccolo, Giuseppe},
     title = {The {NP-completeness} of automorphic colorings},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {705--710},
     publisher = {mathdoc},
     volume = {30},
     number = {4},
     year = {2010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2010_30_4_a14/}
}
TY  - JOUR
AU  - Mazzuoccolo, Giuseppe
TI  - The NP-completeness of automorphic colorings
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2010
SP  - 705
EP  - 710
VL  - 30
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2010_30_4_a14/
LA  - en
ID  - DMGT_2010_30_4_a14
ER  - 
%0 Journal Article
%A Mazzuoccolo, Giuseppe
%T The NP-completeness of automorphic colorings
%J Discussiones Mathematicae. Graph Theory
%D 2010
%P 705-710
%V 30
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2010_30_4_a14/
%G en
%F DMGT_2010_30_4_a14
Mazzuoccolo, Giuseppe. The NP-completeness of automorphic colorings. Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 4, pp. 705-710. http://geodesic.mathdoc.fr/item/DMGT_2010_30_4_a14/