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/

[1] C. Fiori, G. Mazzuoccolo and B. Ruini, On the automorphic chromatic index of a graph, DOI: 10.1007/s00373-010-0923-z.

[2] M.R. Garey and D.S. Johnson, Computers and Intractability (W.H. Freeman, San Francisco, 1979).

[3] I. Holyer, The NP-completeness of edge-colouring, SIAM J. Comput. 10 (1981) 718-720, doi: 10.1137/0210055.

[4] M. Jerrum, A compact presentation for permutation groups, J. Algorithms 7 (1986) 60-78, doi: 10.1016/0196-6774(86)90038-6.

[5] R.M. Karp, Reducibility among combinatorial problems, in: R.E. Miller and J.W. Thatcher, eds. Complexity of Computer Computations (Plenum Press, New York, 1972) 85-104.

[6] M. Kochol, N. Krivonakova, S. Smejova and K. Srankova, Complexity of approximation of 3-edge-coloring of graphs, Information Processing Letters 108 (2008) 238-241, doi: 10.1016/j.ipl.2008.05.015.

[7] A. Kotzig, Hamilton Graphs and Hamilton Circuits, in: Theory of Graphs and its Applications, Proc. Sympos. Smolenice 1963 (Nakl. CSAV, Praha 62, 1964).