ArticleOriginal scientific text
Title
The NP-completeness of automorphic colorings
Authors 1
Affiliations
- Dipartimento di Matematica, Università di Modena e Reggio Emilia, via Campi 213/B, 41125 Modena, Italy
Abstract
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
Bibliography
- C. Fiori, G. Mazzuoccolo and B. Ruini, On the automorphic chromatic index of a graph, DOI: 10.1007/s00373-010-0923-z.
- M.R. Garey and D.S. Johnson, Computers and Intractability (W.H. Freeman, San Francisco, 1979).
- I. Holyer, The NP-completeness of edge-colouring, SIAM J. Comput. 10 (1981) 718-720, doi: 10.1137/0210055.
- M. Jerrum, A compact presentation for permutation groups, J. Algorithms 7 (1986) 60-78, doi: 10.1016/0196-6774(86)90038-6.
- 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.
- 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.
- A. Kotzig, Hamilton Graphs and Hamilton Circuits, in: Theory of Graphs and its Applications, Proc. Sympos. Smolenice 1963 (Nakl. CSAV, Praha 62, 1964).
Pages:
705-710
Main language of publication
English
Received
2009-11-30
Accepted
2010-02-08
Published
2010
DOI: 10.7151/dmgt.1525
Exact and natural sciences