List-Distinguishing Colorings of Graphs - Ferrara, Michael; Flesch, Breeann; Gethner, Ellen (The Electronic Journal of Combinatorics, 2011)
A coloring of the vertices of a graph G is said to be distinguishing provided that no nontrivial automorphism of G preserves all of the vertex colors. The distinguishing number of G, denoted D(G), is the minimum number of colors in a distinguishing coloring of G. The distinguishing number, first introduced by Albertson and Collins in 1996, has been widely studied and a number of interesting results exist throughout the literature. In this paper, the notion of distinguishing colorings is extended to that of list-distinguishing colorings. Given a family L={L(v)}_vV(G) of lists assigning available colors to the vertices of G, we say that G is L-distinguishable if there is a distinguishing coloring f of G such that f(v)L(v) for all v. The list-distinguishing number of G, D_(G), is the minimum integer k such that G is L-distinguishable for any assignment L of lists with |L(v)|=k for all v. Here, we determine the list-distinguishing number for several families of graphs and highlight a number of distinctions between the problems of distinguishing and list-distinguishing a graph.