The NP-completeness of automorphic colorings
Giuseppe Mazzuoccolo
Discussiones Mathematicae Graph Theory, Tome 30 (2010), p. 705-710 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2010-01-01
EUDML-ID : urn:eudml:doc:270968 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1525,
     author = {Giuseppe Mazzuoccolo},
     title = {The NP-completeness of automorphic colorings},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {30},
     year = {2010},
     pages = {705-710},
     zbl = {1216.68118},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1525}
}

Giuseppe Mazzuoccolo. The NP-completeness of automorphic colorings. Discussiones Mathematicae Graph Theory, Tome 30 (2010) pp. 705-710. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1525/

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

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

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

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

[004] [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.

[005] [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. | Zbl 1191.68468

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