The NP-completeness of automorphic colorings

Szczegóły
Opis

Tytuł:: The NP-completeness of automorphic colorings
Autorzy:: Mazzuoccolo, Giuseppe
Powiązania:: https://bibliotekanauki.pl/articles/744108.pdf
Data publikacji:: 2010
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: NP-complete problems
chromatic parameters
graph coloring
computational complexity
Źródło:: Discussiones Mathematicae Graph Theory; 2010, 30, 4; 705-710
2083-5892
Język:: angielski
Prawa:: Wszystkie prawa zastrzeżone. Swoboda użytkownika ograniczona do ustawowego zakresu dozwolonego użytku
Dostawca treści:: Biblioteka Nauki
: Artykuł

Przejdź do źródła

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.

Informacja

Powiązane pozycje