PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2010 | 30 | 4 | 705-710
Tytuł artykułu

The NP-completeness of automorphic colorings

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
30
Numer
4
Strony
705-710
Opis fizyczny
Daty
wydano
2010
otrzymano
2009-11-30
poprawiono
2010-02-08
zaakceptowano
2010-02-11
Twórcy
  • Dipartimento di Matematica, Università di Modena e Reggio Emilia, via Campi 213/B, 41125 Modena, Italy
Bibliografia
  • [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).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1525
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.