The list Distinguishing Number Equals the Distinguishing Number for Interval Graphs

@article{PoppyImmel2017,
abstract = {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.},
author = {Poppy Immel, Paul S. Wenger},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {distinguishing; distinguishing number; list distinguishing; interval graph; list distinguishing number},
language = {eng},
number = {1},
pages = {165-174},
title = {The list Distinguishing Number Equals the Distinguishing Number for Interval Graphs},
url = {http://eudml.org/doc/288067},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Poppy Immel
AU - Paul S. Wenger
TI - The list Distinguishing Number Equals the Distinguishing Number for Interval Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 1
SP - 165
EP - 174
AB - 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.
LA - eng
KW - distinguishing; distinguishing number; list distinguishing; interval graph; list distinguishing number
UR - http://eudml.org/doc/288067
ER -