# The NP-completeness of automorphic colorings

Discussiones Mathematicae Graph Theory (2010)

- Volume: 30, Issue: 4, page 705-710
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topGiuseppe Mazzuoccolo. "The NP-completeness of automorphic colorings." Discussiones Mathematicae Graph Theory 30.4 (2010): 705-710. <http://eudml.org/doc/270968>.

@article{GiuseppeMazzuoccolo2010,

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.},

author = {Giuseppe Mazzuoccolo},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {NP-complete problems; chromatic parameters; graph coloring; computational complexity},

language = {eng},

number = {4},

pages = {705-710},

title = {The NP-completeness of automorphic colorings},

url = {http://eudml.org/doc/270968},

volume = {30},

year = {2010},

}

TY - JOUR

AU - Giuseppe Mazzuoccolo

TI - The NP-completeness of automorphic colorings

JO - Discussiones Mathematicae Graph Theory

PY - 2010

VL - 30

IS - 4

SP - 705

EP - 710

AB - 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.

LA - eng

KW - NP-complete problems; chromatic parameters; graph coloring; computational complexity

UR - http://eudml.org/doc/270968

ER -

## References

top- [1] C. Fiori, G. Mazzuoccolo and B. Ruini, On the automorphic chromatic index of a graph, DOI: 10.1007/s00373-010-0923-z. Zbl1221.05138
- [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. Zbl0473.68034
- [4] M. Jerrum, A compact presentation for permutation groups, J. Algorithms 7 (1986) 60-78, doi: 10.1016/0196-6774(86)90038-6. Zbl0597.68036
- [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. Zbl1191.68468
- [7] A. Kotzig, Hamilton Graphs and Hamilton Circuits, in: Theory of Graphs and its Applications, Proc. Sympos. Smolenice 1963 (Nakl. CSAV, Praha 62, 1964).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.