PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2017 | 37 | 1 | 165-174
Tytuł artykułu

The list Distinguishing Number Equals the Distinguishing Number for Interval Graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
A distinguishing coloring of a graph G is a coloring of the vertices so that every nontrivial automorphism of G maps some vertex to a vertex with a different color. The distinguishing number of G is the minimum k such that G has a distinguishing coloring where each vertex is assigned a color from {1, . . . , k}. A list assignment to G is an assignment L = {L(v)}v∈V (G) of lists of colors to the vertices of G. A distinguishing L-coloring of G is a distinguishing coloring of G where the color of each vertex v comes from L(v). The list distinguishing number of G is the minimum k such that every list assignment to G in which |L(v)| = k for all v ∈ V (G) yields a distinguishing L-coloring of G. We prove that if G is an interval graph, then its distinguishing number and list distinguishing number are equal.
Wydawca
Rocznik
Tom
37
Numer
1
Strony
165-174
Opis fizyczny
Daty
wydano
2017-02-01
otrzymano
2015-09-15
poprawiono
2016-03-23
zaakceptowano
2016-03-23
online
2017-01-13
Twórcy
autor
  • School of Mathematical Sciences, Rochester Institute of Technology, Rochester, NY,, pgi8114@rit.edu
  • School of Mathematical Sciences, Rochester Institute of Technology, Rochester, NY,, pswsma@rit.edu
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1927
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ć.