PDF

Discussiones Mathematicae Graph Theory 30(4) (2010) 705-710
DOI: https://doi.org/10.7151/dmgt.1525

THE NP-COMPLETENESS OF AUTOMORPHIC COLORINGS

Giuseppe Mazzuoccolo

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.

2010 Mathematics Subject Classification: 68Q17, 05C15.

References

[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).

Received 30 November 2009
Revised 8 February 2010
Accepted 11 February 2010