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.
@article{bwmeta1.element.doi-10_7151_dmgt_1927,
author = {Poppy Immel and Paul S. Wenger},
title = {The list Distinguishing Number Equals the Distinguishing Number for Interval Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {37},
year = {2017},
pages = {165-174},
zbl = {1354.05086},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1927}
}
Poppy Immel; Paul S. Wenger. The list Distinguishing Number Equals the Distinguishing Number for Interval Graphs. Discussiones Mathematicae Graph Theory, Tome 37 (2017) pp. 165-174. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1927/