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
topHow 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 ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.